I had this problem on my BE 10.1d server backing up my Exchange 2003 (Standard) server only the "corrupted" file was located in my users' "Junk E-mail" folder.
It didn't happen all the time and at times it was a different user. But the commonality was that it was always in the Junk E-Mail folder.
Eventually I decided to research the error in the Veritas support site and found this:
http://seer.support.veritas.com/docs/261457.htm
Once I applied the fix (a registry hack), problem never came back.
As a precaution, and because I also have the luxury, I perform a random Exchange mailbox restore once every two weeks. I also replicate my stores and have other secondary backups in place. :)
Hope this helped.