Adding User

I am trying to add a user but it keeps on telling me “Username/email already exists”. When I look under “Users & Account Info” → “Other Users” the user I try to add is not listed. However, when I use some arbitrary letters for the username it works. So it seems that the user I try to add was added before, then deleted but somehow it stayed in the system so I can’t add it anymore. Has anybody else experienced this? Is there a way to use the same username again?