I have an user that was deleted from Unity, when I try to add him back I get the "the alias specified matches an alias already existing in the directory" error message. The user still has his AD account and Exchange mailbox. I don't want to have to delete these accounts unless absolute necessary.
I have good news for you.
You do not have to delete user out of AD and Exchange, just remove the Unity properties.
Use this tool