I have found this passage in Runciman's A History of the Crusades:
In 1040 six brothers [...] took control of the city of Melfi [...].
[...] Henry III supported them in order to gain control on the region
that he contended with the Eastern Empire. The German Pope, that he
had elected, did the same, as he was scorned that the Eastern
Patriarch had jurisdiction on an Italian diocese. In little more than
twelve years, the sons of Tancredi had imposed their control on the
Lombard principalities and had pushed the Byzantine towards the edges
of Calabria and the shores of Puglia, they were threatening the
Westerly cities* and in their raids they pushed North, through
Campania in the neighbourhood of Rome. The Byzantine government was
alarmed [...] but the Normans easily dispatched its small army, but
had more success with diplomacy as the new Pope [...] Leo IX, was
nervous. The Normans had achieved more than he and Henry III had
expected.
- From the context these are Naples, Amalfi and Gaeta.
The translation is mine as I have the Italian translation of the book.
I think that, from this passage, we can evince that the Normans indeed had some degree of legitimacy. What happened later, in that the Pope confronted the Normans, is indeed correct. However it refers to a later development, and also (likely) to a different Pope.
This is confirmed by another snippet that comes from Wikipedia's page about Drogo of Hauteville (unfortunately I do not have access to any of the texts referenced in the article).
On 3 February 1047, while the Emperor Henry III, was visiting southern
Italy, he received Drogo's homage and invested him with all the
territory which he already controlled. After this Drogo began using
the title "Duke and Master of all Italy and Count of all the Normans
of Apulia and Calabria".
(emphasis added). I would dare and say that the Normans' conquest of Southern Italy was mainly a consequence of an Imperial project, while papal support only came insofar as the Pope was (in that particular timeframe) a puppet of Henry III.
The Holy Roman Emperor wished to re-establish his control on the whole Italian Peninsula, as he considered himself the successor of the Western Roman Emperors. This involved defeating the Byzantine as well as the Lombards (who settled the Appeninnes) and the Saracens (who occupied Sicily). He likely hoped to use the Normans as pawns, but when the latter consolidated their control on the whole region, he realized that the situation had gone out of his control. The new political entity was much stronger than the sum of its parts. So much so, that all previous Christian contenders in the region, the Byzantine, the Pope, the Lombards and Henry III joined their forces against the Normans.
This awkward coalition was however defeated in the Battle of Civitate, after which the future Kingdom of Sicily became one of the major powers in Europe, holding important roles in the Crusades, in the struggle between the Pope and the Holy Roman Emperor, and even attempting to conquer the Byzantine Empire.