I think it all depends on what the REAL Pk value (percentage kill) for the air-to-air missiles is. (Less so SAMs, but them too.) In Vietnam the AIM-7 Sparrow claimed 59 kills for 612 launches, or less than 10% Pk, only two of which were beyond visual range (BVR). (That is partly because Vietnam rules of engagement limited BVR launches.)
I would imagine that a good chunk, if not the majority, of fighter vs. fighter engagements will be within visual range, while BVR attacks would be reserved for bombers. So the way the AIM-9 Sidewinder stacks up against the AA-2 Atoll and AA-8 Aphid will be a significant factor. Given general American superiority in electronics I would imagine -- these are out-of-a-hat numbers -- Pk for the AIM-9 being twice that of the AA-8 and 4 times that of the AA-2. The other battle is the AIM-7 Sparrow versus a host of Soviet SARH missiles, and again, I think Western radars and missiles might well have proven to be superior, even if they still only had Pks of 20% or so for BVR attacks. The AIM-54, although I don't think its reliability was questioned in OTL, won't be as much as a factor because where there are AIM-54s, there are Standard SAMs, and one could cover for the other if need be.
I do see the validity of the argument than an F-15 can only shoot down so many MiGs. You'd have a lot of situations where an F-15 was engaged by, say, five MiG-21s, and the Eagle scores, say, 2 Sparrow kills and a Sidewinder kill before it has to face the reality of four Atolls getting near the tailpipe. But all four might go off the rail unguided. And then it's down to guns, and pilot skill. Also, all this said, as long as the F-104s are kept to a minimum then NATO has a fighting chance. Ehh, one of those is a gate guardian at a nearby museum, it's a pretty plane but it does have to be said that half its aesthetics are due to the cute little tiny wings.