Not sure if this has been mentioned but the art of 'name freeing' is common place in MMOS; GW2, Wildstar, WoW; they have all done this before. The character itself doesn't have to be deleted, all SE would need to do is remove the line of script dictating the name you chose.
When you log in all the game would do is request you create a new name for your character, that still exists on your account. I would agree, however, that any characters with their names being removed should have been in-active for at least 2 years (in my eyes.) Level shouldn't *really* matter.