Looking at the info you provided, as well as other stuff I managed to find, the NK-25 looks like a damn good choice for our MiG-25 successor: about double the thrust of the R-15, reasonably close to the same size, and good fuel efficiency (it powers the Tu-22M OTL). Also, the Backfire had its first flight in 1969, with entry into service in 1972. Assuming that development for the Backfire proceeds roughly OTL, you could actually end up sticking the NK-25 into the super-Foxbat I postulated in option 2. Assuming an empty weight of around 22-23000 kg (slightly larger than the MiG-31), my calculations give a maximum T/W ratio of 1.26. Which is damn good for the early 70s (as well as being superior to the F-15C). The main issue I can see is how the NK-25 will perform at high mach numbers, considering that the airframe its designed for (Backfire) only goes up to around Mach 2. This can probably gotten around with clever intake design though, to get the incoming air down to subsonic before it enters the compressor section.
I'm not entirely sure that thrust vectoring capabilities are entirely within the capabilities of Soviet aircraft design in the late 60s/early 70s. Besides, I'm not entirely sure they'd even be necessary. This hypothetical MiG-25 variant (25X?) isn't going to be screwing around down low shooting R-60s at A-4s and F-16s, it's going to sit at high altitude 50+ km off, shooting long range SARH missiles at B-52s, B-1s, and the like. Although I do agree that it would need more turning ability than the Foxbat has in OTL, at least to be able to get out of dodge if it gets jumped by a couple of Phantoms or Falcons at low altitude. I think that can be covered under using better materials and making some improvements to general construction practices (when examining the MiG-25 in 1976, it was found that the aircraft was hand-welded and had exposed rivet heads in some areas).
With regards to using a better missile rather than a faster aircraft, I agree with the sentiment that a better missile is going to be extremely useful, however putting the firing aircraft at a higher speed and altitude is going to provide an advantage. To put it simply, the more kinetic energy the launching aircraft gives a missile, the less the missile has to spend catching up to the target and climbing toward it. As a result, the missile is going to be able to maneuver better, as well as engage at a longer range. Conversely, an aircraft with better speed and altitude capabilities is going to be harder to hit, especially in a tail chase situation.