The only way it could work would be to have a list of first names and a list of names per country, and a list of automatic rejected combinations. (famous people and unhappy combinations like "Jean Cule" like Perpete said).
I don't have a problem if a combination is used a lot, you already have a thousand John Smiths in the game as it is anyway.