We just had issue with our exchange which we have to restore the exchange. Now, Unity email messages are not deleted from the email inbox after we delete the voicemails from TUI/phone and vice versa. But We did get the Unity email messages in the user email inbox. We are currently using Cisco Unity Connection 8.6 and Exchange 2003.
Someone has similar issue in the past that can give us some light in our current issue
I am making a few assumptions here, but I think your issue is going to be related to the message synchronization properties discussed here.
You might consider what you've experienced to be simlar to a synchronization issue relative to Single Inbox because you restored messages that Single inbox already acted on. I don't have a solution for you but thought i would point out this article that may help you understand what happened and find a way to resolve.
Thank you for your input.
I have read similar article about disabling and reenabling the Single Inbox sync but it is still not working. I did it in user account and the unified messaging service.