I've never run into this problem, then again I tend to use names from random name generators and obscure books. Most of the people that ask for this seem to want a name from something popular, or a name that is a witty saying/phrase rather than an actual name. Just come up with your own names, it's better all around. ^^

Isn't Gilgamesh known for being one of the unofficial RP servers? The level 1 character could be for that. *shrugs*