Other than the “external database” option, the only other sources of name information I can think of are:
The mind of the person being mapped
The mind of the person reading the map
A sort of consensus of how everyone in Hogwarts knows someone
I feel that picking someone’s name from their own mind seems the most elegant and consistent. It doesn’t handle babies (Before the parents choose a name, can a baby even be said to have one? Babies would have to be special-cased regardless), but it does allow arbitrary people to be mapped (multiple strangers being indistinguishable from each other seems like a serious flaw in a security system) and requires no external registry. On the one hand, it seems like interrogating the mind of every human is vastly more complicated than just looking up the name in a database, but to the kind of epistemology which would seem obvious to a 9th-century witch or wizard I can see it being “obvious”.
(And to respond to your question about Pettigrew in the great-grandparent, I would assume that the map skips over animals entirely, which would probably include animagi. This would tend to lend a slight amount of weight to my “the map displays your name as you know it” theory, as if the names came from how everyone else around you knew you there would be no reason not to include pets.)
If my theory is true, it raises an additional interesting question: Is it possible to obliviate yourself selectively so that you lose all knowledge of your own name? (Possibly storing the memories in a pensieve first so you can recover them later) And if so, is the map the only piece of the Hogwarts security system which might be impeded by this?
A further idea: Professor Quirrel is shown to take a very loose approach to identity and names (“Identity does not mean, to such as us, what it means to other people.”) Possibly Quirrelmort is the constant error, not because his name is wrong, but because he doesn’t have a name attached to his marker at all.
I don’t remember what post it was in response to, but at one point someone suggested “optimal” as a much better substitute for “rational” in this type of post, partly to reduce the use of “rational” as an applause light, and partly because it better describes what these posts are generally asking.