On the way to Mongolia we will cross a dozen countries, many of which have very strict and sometimes rather complicated regulations that govern how foreigners can enter and move around. Coming with your own car doesn't simplify things either.
Once we leave Europe, every country on our path requires us to have a visa in order to enter. Without the proper visa, we'd simply be turned away at the border in most cases. Most visas have restrictions: they are valid only for a certain amount of days, allow only a limited number of re-entries (usually one), have fixed entry and exit dates (that you sometimes cannot choose freely), or fixed border crossings (never change your plans).
Some visas are valid for as few as 5 days. Combined with fixed entry and exit dates, this requires very accurate trip planning. Some visas are valid for 90 days, but the 90 days start running at the day the visa is issued, requiring very accurate planning when acquiring the visa. Single entry means that once you leave, you're not allowed to re-enter even if you have days left on your visa. I don't think this will be a problem for our trip, as we're visiting every country only once.
In most cases, visas come in the form of stickers and stamps in your passport. To get these, you have to physically mail your passport together with a complicated application form to the embassy, and wait until it comes back, hopefully with the visa. This can take between 5 days and 6 weeks, depending on the country (and your luck), and they can refuse with no explanation. This also means you cannot do the applications in parallel, and you cannot travel while your passport is "traveling". Some visas can be gotten "on the go" (in the embassy of a neighbouring country, for an extra "express" fee) or directly at the border (also for an extra fee, of course).
Some countries require a Letter Of Invitation ("LOI") together with the visa application. This was probably meant to make sure you are hosted by somebody while you are there, but in fact it's just another source of money for local tourist agencies (who will happily write you such a letter for a certain fee, usually also coupled with booking a hotel). Some countries even require your fingerprints, a detailed itinerary, confirmations of booked hotels, a recommendation letter from your employer (!), and a letter explaining the reason for your travel.
They are also costly. While each single visa is not outrageously expensive (on the order of 50-150$ each), it sums up. We will require between 7 and 10 visas (depending on how our plans work out).
Fortunately, my fellow travellers are Norwegian and Swedish, and I am Swiss, and therefore we don't need visas in Europe, and have similar restrictions outside Europe (this makes planning a bit easier).
We will make use of http://www.thevisamachine.com as much as we can, though they cannot get all required visas and permissions we need (and they cannot speed it up, it still takes months). The rest we'll have to get ourselves or with the help of another travel agency.