The trans-Siberian route to the Far East opened up at the end of the 1960s. It represented a huge saving in time and fuel over the Anchorage stop. For several years, there was an obligatory transit of Moscow and I believe that Russian navigators were taken on board to help guide the aircraft (basically to avoid it overflying sensitive areas). This gave rise to tripartite ‘competition’ on the main routes – BA, JAL and Aeroflot on London-Tokyo, AF, JAL and Aeroflot on Paris, etc.
Finnair was (I think) the first to fly nonstop Europe-Tokyo, over Siberia, and for a while enjoyed a nice niche in sixth-freedom traffic from the main European cities, via Helsinki. As the other airlines upgraded to better-equipped long-range aircraft, they pressed the Russians to be allowed to do the same. This of course threatened to leave Aeroflot at a huge commercial disadvantage since they didn’t have nonstop rights (and no capable aircraft in the unlikely event they would ever get nonstop rights) and had to operate via Moscow. Consequently Western airlines were obliged to pay ‘royalty payments’ to Aeroflot for the right not to make an intermediate call, in direct contravention of international air law.
This is still going on and currently costs the European airlines somewhere in the region of $300 million annually. Nobody knows where the money goes. The European Commission is currently negotiating with the Russians to get these charges (a) frozen, as demand for extra flights increases, (b) reduced and (c) eventually abolished, with 2014 as a target date. The Russians simply don't want to know.
As a PS to the above, there was a time, around 1973-4, when BA were investigating a Concorde service LON-TYO with a single stop. Range limitations meant that the stop had to be very close to the midpoint of the great circle between the two. So they stretched a string around a globe and checked their airfield charts to find somewhere about half way – the only candidate was a place callrd Norilsk. So next time they had a bilateral meeting with the Russians, they tabled a request for a London-Norilsk-Tokyo Concorde routing. The Russians looked at each other in amazement for a few seconds, then fell off their chairs laughing.
Another PS re overflying sensitive areas, there was a history of Cubana Havana-Montreal flights making unexplained diversions from their alotted airway over the US to pass over and presumably photograph military installations. When it happened several times in a short period (early 1980s??) the Americans either gave them fighter escort or withdrew their overflight clearance and made them go the long way round, I can’t remember which.