Exchange 2007 SP2 has introduced some new Mailbox Access Auditing features to help log events when users access folders and messages either in their own mailbox or another users mailbox. I wrote a whitepaper on these new features at http://technet.microsoft.com/en-us/library/ee331009.aspx. This new access auditing will log accesses to messages and folders which some customers have been wanting for a long time. So if you attempt to access another users folder and open or read a message, Exchange will now log events in the new Exchange auditing log on the server. This only shows you the path of access to message and folders, but does not specifically log deletions of messages in users folders.
The whitepaper also discusses how you can setup auditing to track configuration changes to Exchange related objects in Active Directory, so that if an administrator made a change to an Exchange configuration object that caused an outage, these events will now be logged on the domain controllers security event log. If your DC’s are Windows 2008, you can see what the previous values were and what the newly changed value is, so if you need to change it back to the way it was before the outage, you have a rolling log of all of these changes.
If you have some time and wanted to read more about it, see the above link for more details. This took a lot of time and effort on my part to pull this together and test most of the configuration auditing pieces to ensure that we were logging the correct data. Hope you enjoy it.