Currently there are loads of users with almost no playtime who haven’t logged on in months-years. These users have often taken usernames that other players might want.
So, I think you should perform a purge of all current characters that have not logged on in 6 months and have less than 2 hours of playtime. I think this would clear up quite a few taken names and allow new players to pick a name more freely and not have to use special characters or extra characters to get the name they want.