Long time ago I created my prot monk and decided her name to be Luna. That's a common name, I know... and since her first name means moon, I thought about taking some moon-based word as a surname too. Everything I deemed worthy seemed to be taken already and I had to pick up the one she has now (and I have grown to like her name a lot

).
Then, just few days after the creation, I was waiting for my guildee at Ascalon (in post-searing) and there, right in front of me, appeared the character with the name I had chosen for her in the 1st place. I had to use all my willpower not to tell her to delete that character and let me take that name
And since the early stages of character creation (I used to do a lot of deleting and redoing), I have learnt that it's a lot easier to find out one good Surname and use that with all my chars, than trying to invent loads of cool new names which most often are already taken.