One way to do it is to remove the names from character deleted a LONG time ago.
I don't know why a deletet character is laying in the system. I can see the point that if you made a mistake you should have a chance to ask someone to undelete it, but a level 4 that I deleted 10 months a go is not nessesary to stay in the system.
I notice this when I open a chat client on the webpage. I was offered to log into something like 12-13 accounts where some of them was deleted a LONG time ago. I wonder what happend if I chose one, but in fear of loosing some of the characters I actualy like to keep I don't dear try.
If FC feel to unserten about peoples ability to delete there own characters I suggest that you keep a character in the database in max 10+"level of char" days in the database. This will give people one month to reopen a accidential deleted level 20 character and 7 month for a level 200.
