I recently learned about a useful tool for troubleshooting Unity/Exchange mailbox issues. It's located in the \CommServer\TechTools folder, and it's called MBXSuite.exe.
To use it:
1) Select the user whose mailbox you want to test with.
2) Select the Unity service account you want to run as--usually UnityMsgStoreSvc.
3) Check "Verbose Diags"
4) Click "Logon Mailbox" and check the Diagnostics pane for errors.