Allright, I'm going to throw in my 2 cents.
First of all, in MXO our characters are more than just toons with names. They are "characters" that play into the storyline of The Matrix...I think Anome's character has been inactive for a while, but I don't think that a new player should name his self Anome. While this is an extreme case, the same can be said for other characters. I'd cry a bit if I saw a new player named TasteeWheet or Skyscream. To allow new players to take old player's names is to completely ignore the the canonic (word?) nature of MXO.
Of course, as we have seen, this creates clear problems; any created character is technically part of canon, including low level characters that were created and are now ignored. Completely ignoring the technical issues of character names, my solution would be that in order for a character name to remain tied to a certain character, that character must reach X level, have X ammount of play time, and complete X objective. Once these are done, unless that character is deleted, a character name should not be accessible to players.
Alternatively, if a wipe was neccessary (which maybe it is) an email could be sent to every account owner (of course, I don't trust that, but something of the sort could be done) informing them that unless their account is re-activated, all the characters will lose their names/be deleted.
Basically, I don't think names should be easilly reasigned. Maybe I'm biased, being a returning vet and all. However, if after 6 months my character's name was gone, I wouldn't have resubbed- while I've had friends who have had trouble creating names, but they always found a name in the end and played.