If you look at the Gazala battles the DAF had numerical superiority (but I don't have the figures at hand) but couldn't prevent the axis planes from providing critical support in the reduction of the allied "boxes" that eventually led to the fall of Tobruk, I don't call that air superiority. The LW and Regia Areonautica ground support units were equipped with Ju 87 and CR 42s not exactly the sort of planes that could operate without at least air parity.
The problem with the DAF was that it operated large numbers of level bombers (Welligtons, Blemheims) that had few viable targets in the desert. It also got very low priority on Spitfires that mostly went to Malta leaving the DAF with Hurricanes and P40s that were not as good as the German Me 109.
As Steverdodgers801 pointed out it's difficult to make real comparisons between air availability in the Med, a lot of missions in support of Rommel in 1942 were flown by Crete based planes and axis units could swing from bombing Malta/naval interdiction to ground support more easily than the more tactically rigid British whose only reliable base in the central Med was Malta and lacked bases in the Western Med for most of the campaign.
Digging up some figures on plane availability would help this discussion.
According to Terraine at the start of the Gazala Battles the DAF had fewer serviceable aircraft C 290 (plus 700+ elsewhere in the ME) against the Axis total of C 650 (plus a further 200 in Crete and Sicily with the range to hit Libya)
The DAF had a wing of light bombers (@ three squadrons) and two wings of fighters (@ 4 Sqns P40 & @4 Sqns Hurricane) All 211 Group fighters were supposed to be fighter bombers from 1 June 1942, but only four sqns had adapted at that date. The first spitfire sqn joined the DAF on the same date. One reason why Spitfires were not deployed earlier was because of the concerns about the aircraft's suitability for operating from rough airstrips in view of its narrow under carriage.
It is true that the German Me109F and G (and the lesse acknowledged MC202) had a superiority in air to air fighting over the P40s and hurricanes of the RAF. However, there were relatively few Germanand Italian top quality fighters and the tactics they adopted tended to be hiyt and run. The result was that the “jaegerflieger persued a private war while the landser cowered in the trenches.” ( E R Hooten) This was a touch of Trenchard over the trenches with the DAF pressing on while the German aces racked up a score. The DAF flew 1500 sorties in the first five days and lost 50 aircraft (20% strength) The biggest air battle with both sides employing close air support was over Bir Hachiem, defended by the French and surrounded by the Axis. . The RAF flew 1500 sorties in support ove rnine days at a cost of 20 aircraft. The Luftwaffe flew 1400 and lost 15 while the Italians lost at least five.
The other issue was that Malta was the seen as a bigger priority, by both sides – which is the other reason why Sptifres went there before Egypt. As Kesselring pointed out when he tried to stop Rommel's 1942 North African adventure was that the Luftwaffe did not have the resources to sustain an air offensive over Malta and North Africa at the same time.
I don't think it was a case of the Med depriving the Russian Front of German aircraft but that the Russian winter prevented their use on this front and hence their availability in the January to March periods for North Africa. Russia always got priority.
The Germans might not have needed the Luftflotte 2 assets on the Eastern Front in the Summer of 1942. However, in Dec 1942- Jan 1943 I suspect the Germans trapped in Stalingrad might have appreciated the availability of the aircraft maintaining an air bridge to Tunisia, and the panzers lost there..