The user account likely still exists under exchange mailboxes (probably was not deleted). Delete the mailbox from exchange and users if it is there and try again. You can also try importing that existing account into unity and just deleting the messages (if any) and then set it up that way.
Yes, its probably true, the exchange mailbox is still there. But remember also, if *just* deleted the user, then tried to recreate it, AD will not replicate the changes in it's own database for approx 10-15 minutes. If it's across a WAN connection or you have a large subscriber database on unity, it will take even longer.... Use exchange the hunt out the random mailbox and clean it up. You can also check Users and Computers MMC on your AD to see if they are still in there for some reason.
I'm not able to access my old voice mail messages all of a sudden. The recording says something like 'the message is currently not available'. This has never happened before in all the years I have been using this system. I have t...