For others here is a complex Unity problem and how I fixed it.
Unity 5.0(1) Unified Messaging with a user who wasn't getting voicemail in Outlook. The below would show up in Event Viewer log file when leaving him a message. Message would be in e:\commserver\unitymta\failed
Event Type: Error
Event Source: CiscoUnity_Notifier
Event Category: Run
Event ID: 1034
Time: 2:18:21 PM
Mailbox logon failed for user cn=Mark.Dows,cn=Recipients,OU=Duluth,O=Patron. This can occur if the user's message store is unavailable. When the message store becomes available, resync the user from the SA by refreshing the MWI status on the user's Messages page.
His real name is Mark Dowis and we couldn't figure out where/why Unity was showing the mis-spelled last name. The fix was to use adsiedit to change LegacyDN from Dows to Dowis, the Bulk Subscriber Delete and then Import.