Put in a recycle bin that lets people undelete characters. That'd eliminate most of these requests. It's sort of a "lock-your-keys-in-the-car" thing where you immediately know you've made a mistake.
I like it. Make it a 24 hour window to go back on the delete (that way there aren't a lot of player names saved in the "recycle bin", and they don't stay there very long.)