Veritas fails with Corrupt emails

I have an Echange 2003 site running Veritas which is doing a full backup of Exchange including individual mailboxes.
It regularly fails saying it has found a corrupt message at the top of information store. I can go into Outlook and delete the relevant emails and the backup will succeed, however the next night there’ll be new corrupt emails.
What would be causing this? Customer is not happy having to keep deleting corrupt mail and want a fix!
Thanks