An era-specific system has been talked about a lot, but there are (as always!) some problems with it. What do you do for civs like America? Just scale the time period, I suppose, so that Colonial American people would be "ancient", and so on. The actual programming is trivial; it's the sorting of all the names that is hard!
Here's an idea. (I hope I do not end up regretting mentioning this...) For a long time I have been toying with the idea of religion-specific great prophets. It always seemed odd to me to have Moses born in a Hindu city, or Abu Bakr in the Christian holy city. I haven't looked into it much, but creating a new mechanism for naming just the prophets does not appear that hard.
Basically, there are two ways to go about it: by city religions, or by national religion. If a city has Hinduism only, then only Hindu prophets will be generated from that city. One with Judaism, Islam, and Taoism would have an equal chance of generating any of those kinds.
The other way is to look at the national religion and work from there, but what if you are running free religion?
The downside to religion-specific naming is that you could still take Moses, a Jewish prophet, and use him to create the Dao Miao, which kind of makes the whole thing moot. This also conflicts with my civ-specific convention, so I'd have to scrap that as far as the prophets go, or be forced to come up with names for all seven religions (plus the eighth - no religion) for every civ!
But it would still make for an interesting and more flavorful game nonetheless.