Hi -
When you configured Unity, did you specify that deleted voice messages go into the Deleted Items folder? Also, if your Exchange is offbox, there may be a policy to keep messages in Deleted Items for so many days. There are several ways to check to see if mail still exists in the mailbox, using Exchange System Manager or even Outlook. You can log on to the user and configure Outlook. Check the Deleted Items folder.
Ginger