Thank you Halibut!
I've been following this post for awhile now and just now saw your addition. It worked like a charm...well kinda...I had to tweak the MS instructions a bit.
Until now, I had to deselect the Outlook Message Manager items in Veritas in order to get a successful backup. In fact, you will only see the messages in question in Veritas, you cannot see them on your Exchange server.
About the client/server being out of synch, this user had no rules set up in his Outlook, so perhaps that's one reason but not the only reason.