Comment by jandrewrogers

It depends on the country. The US has the ability to do the equivalent of deep "duck typing" with almost no documentation even if you've been off the grid in the developing world for a long time. This is a case where the intelligence apparatus works in your favor. They can know you are a US citizen with high probability absent obvious evidence of such.

Of course, if you fall into a crack that is beyond their reach you will almost certainly have a more difficult time. For a variety of historical reasons, there has been relatively little reliable documentation of American citizenship so the system adapted to that reality.