score:12
First of all, if you go by the USA definition of "branch of the military", the Soviet VDV were not one. Until the dissolution of the USSR in 1991, they were a part of Ground Armed Forces branch — a quite independent one, but still less independent than, for example, the US Marine Corps. Moreover, due to the difference in how budget was allocated in the USSR and in the USA, the Soviet Armed Forces did not see the same degree of inter-branch competitiveness as American ones.
EDIT: A bit of explanation on structure of Soviet military in the relevant period (1946 to 1970s): The whole military was officially called "Armed Forces of the USSR" ("Вооружённые Силы СССР"). This structure included:
Central military administration ("Центральные органы военного управления") - besides administration, this branch included military intelligence service (the now-infamous GRU), military topographic service and military political department (that's department responsible for political officers);
Soviet Army ("Советская Армия"):
Navy of USSR ("Военно-морской флот СССР") - note that while this branch was directly included in main structure, it was more analogous in organisation to single component of Soviet Army, for example Ground Troops; it included submarine forces, surface forces, naval aviation, marines and coastal defence forces but these were not separated in command structure as, for example, Ground Troops and Air Forces were, but were divided amongst regional Fleets, each of which would have every type of troops - same as Ground Forces.
Logistics of Armed Forces ("Тыл Вооруженных Сил") - training facilities, railroad and automobile transport troops, medical service;
Border Troops of KGB of USSR ("Пограничные войска КГБ СССР") - these were a part of KGB and usually administrated by KGB, but in case of war command would be transferred to the military;
Internal Troops of Ministry of Internal Affairs of USSR ("Внутренние войска МВД СССР") - same as above, but with MVD instead of KGB.
Only the entries denoted by numbers would be referred to as "branches of military" in Russian, the rest would be "types of troops". Ground Forces of Soviet Army included:
As you might notice, this structure is not designed for independent actions of different types of troops (or even branches, as it would be in U.S. military), but rather for their interaction. For example, VDV did not have their own aircraft (not even helicopters!) - they would have embedded troops from Air Force for that purpose; or navy marines were not supposed to conduct operations other than base patrol on their own, but rather would be, for example, spearheading landing operations while supported by Army troops in second wave, or supplementing coastal defence and attached Army troops in defensive operations. So where USMC would be mostly autonomous as soon as the troops were deployed from the ships, unless a specific mission called for outside expertise - VDV would be expected to constantly act in tight cooperation with other forces.
END OF EDIT.
Secondly, while you are rightly pointing out that neither Crete nor Market Garden — I'd also add soviet Vyasma airborne operation to this list — saw the airborne troops perform as expected, that did not lead either the Axis or the Allies to abandon the concept. They just changed the way these troops were used. Same with the Soviets — they learned from their mistakes. And Margelov, as the first post-WW2 commander of VDV had a significant role in this reformulation of the role of airborne forces.
Drawing on his World War 2 experience, he insisted that since airborne forces have to fight the enemy in isolation, they need to have the whole array of options ground troops would have. Thus, to be successful, airborne forces have to be mechanized — both to be able to quickly move into positions after deployment, and to have enough firepower to defeat the opposing forces. He consistently pushed for development of air-mobile vehicles. As a result, VDV evolved from an infantry force supported by a few light vehicles to a fully mechanized force complete with APCs, self-propelled artillery, command and engineering vehicles — less powerful and armored than their purely land-based counterparts, but instead capable of being dropped along with the infantry. And, of course, VDV still had its traditional first pick of new recruits.
This produced a force that could be quickly moved and deployed anywhere its aircraft could reach, and powerful enough to hold its own against a conventional army. That led to an interesting result — most VDV operations did not involve airdrops. Instead, they were used as a quick-response troubleshooting units, deploying from already-controlled airstrips or via helicopter insertion.
And there you have it — a force that due to its quick response time will be the first to face the enemy; that has its own unique toys; that only gets the best people. I'd say the prestige was the natural product of this combination.