what paperwork would have had to be missing to prevent a jet from landing anywhere?
Nothing really that couldn't be faxed/emailed over to arrive before the jet and presented on arrival, or a phone call made to the authorities of said country to explain the situation - (but who knows what could happen with the authorites of those Banana republics). The only thing I can think of would be in the case of the USofA, the passport info taken at check-in has not been received so they could not pre-screen for any "undesirables" on the flight, but normally they won't let a flight depart in the first place unless the info is sent.
It would be an extremely rare situation for an a/c to turn back just because of paperwork problems, but not rare to turn back because of engine problems.
Just because someone said it was paperwork, doesn't mean it was right. The story could have changed several times due to "chinese whispers" as the info passed down the line to the person you heard or they didn't understand the nature of the real technical reason and so made something up that they thought passengers would understand - happens all too often unfortunately.
