Ah, those Non-Scheduled flights...such a big fun!
Take Russian overflight using the Trans Siberian routes...for example RJAA - EHAM. The aircraft is let's say registered in one of the countries which does not have the bilateral agreement with Russia (and its National Carrier, i.e Aeroflot), operating under AOC as Non-Scheduled Commercial passenger traffic. It will only be a single overflight.
If there is no such agreement - please find your way via China-Kazakhstan, as you will only be permitted to overfly Russian territory entering via Caspian Sea, and then via Rostov FIR towards Belarus. Or bypassing Russia completely. You did not plan a fuel stop for that? Well...you better do somewhere in Astana or Baku
What I am trying to say is that many believe that there is no such thing as Bilateral agreements for Non-Scheduled commercial flights, and they are only in force for scheduled commercial service. Russia, however, is standing aside and it is one of the countries (if not the only one) where you must have this agreement with the Nat. Carrier before even attempting to submit your overflight request to FATA. Try to find it in Russian AIP, it's not there either!
Private flights are easy peasy stuff comparing to the above as long as you know lead times for permit applications, right contacts etc...
Another pain is - those flying under Temporary Airworthiness Certificates, but it is a different story.