Steve,
I would make sure Unity is fully patched with all Windows Updates using the ServerUpdatesWizard from cisco.com. Also, verify that the time is correct on your mail store (if it's not installed on the Unity server).
A way to test an off-box mail store solution is to force Unity into UMR by stopping the CuMDBStoreMonitor service, leave a message and listen to what time stamp it has on Unity before it gets delivered to the mail store. Then re-start the service and let the message get delivered to the mail store and see if there is any difference in the time once arriving at the mail store.
Hope that helps,
Brad