In Thailand there are about a million people born in Thailand who lack national ID cards. In some cases this is due to poor record-keeping or records lost in the tsunami, but there are also many “hill people” (ethnic groups like Akha, Karen, Lisu, Hmong, etc.) who are deliberately denied ID even though they’ve lived in Thailand for generations. (Some have special ID cards just to acknowledge they lack national ID.) These hill people are ineligible for all government services and risk arrest just to travel. To obtain national ID card would cost them two year’s wages or so – difficult since they can’t work legally.
As a different anecdote, I once worked with a high-ranking Silicon Valley engineer, ethnic Chinese, with U.S. government security clearance. He suddenly lost his citizenship (and clearance!), as did many of his relatives. Turned out his alleged grandfather was just some guy who needed some extra exemptions on Form 1040!