We have a large enviroment here and there a "couple cooks" in the AD kitchen from time to time. When we deployed Unity, I created a voicemail only domain and had the META guys push me a copy of their AD to my AD so I can keep the account names, first last, alias, etc. This has been great. Except when this scenario happens what you are talking about.
Security had a problem with an account in the production AD. They deleted the account and recreated it. META, pushed me a disabled flag on the account leaving me trying to figure out why I cannot view the profile of this person in Unity.
Sure enough, the account was recreated with a new alias, different SID in AD. Unity did not like that so much and pretty much made the account unusable. A good way to test is to go your Unity VM messenging store and see if you can log into through OWA to see if the account works:
http://mail.unitymessengingserver/exchange/alias
login with domain\unitymsgstrsvc (since it has rights to all mailboxes)
The account may look fine in AD and it's not disabled, but if you look at the Exchange Advance properties, you will probably see the security properties of "Self" and that's it. The account has lost all permissions. You can try and manually add them back in, but you are better off just starting over.
I always tend to ask the subscriber questions like "have you had any problems logging into your workstation or email? Have you called the help desk lately regarding your login account to AD" This usually puts a red flag up for us that the account has been altered someway from the AD guys and pushed to us, which broke the Unity account connection.
95 percent of the time, this all works fine. AD Admins are not supposed to delete accounts in AD at all. Lazy admins delete accounts, good ones figure out why it does not work.
anyways.. maybe this long winded story will help point you in the right direction
