Would the group of literate people contain enough people also concerned with accurate record keeping? They seem to be relatively distinct and not necessarily overlapping skills or interests. And plenty of record get lost no matter how well they're kept. Fires, floods, disinterest, etc.

But for some people such a lineage is like a vanity address. And they will go out of their way to dig up a connection like this and absent that they will create one. Throughout the world it's pure gold especially for politicians, it establishes the kind of historical legitimacy and connection to land and country that's far more exclusive than "just" joining the military (the other common vehicle for populist patriotism, even if one would never be exposed to any real danger).