There's only one way around the whole 'finite names' thing I can think of. It's a system employed in Anarchy Online (and I think also 'Matrix Online', and a few others).
Basically, your primary name is your 'nickname'. It's the name that the system responds to, and the name that appears in chat/groups. But you can also choose first names and last names, which can be duplicates of other names. OOC, people are referred to by nicknames, but IC they're often ignored - going by the first and last names you chose yourself (which, outside of RP, are inconsequential). The nicknames are unique, and can be virtually anything, giving an unlimited number of monikers.
It would get around the problem of 90% of the decent names being taken by people who'll never come back (plus their alts) and may even force people to think harder about their characters (i.e. "So, where'd you get a nickname like that?")
Just, thinking out loud here...