Hello,
Are you using the Advanced Open File Option to backup Exchange ? Such problems occur when antivirus scanning is running during the Backup Job. Either stop the Antivirus scanning during the Backup job and when not feasible, exclude the files that are being backed up during Antivirus Scanning during the Backup Job.
Also delete the corrupt files.
Have a look at the following document :
http://support.veritas.com/docs/266074
Also check the rights the Backup Exec account(BESA) possess over Exchange. Follow the document to check whether sufficient rights are given to the BESA to backup Exchange. Check the following.
Making BESA full Exchange Administrator.
Removing BESA from Domain Users.
Recommending remove: Corrupt email message.
http://support.veritas.com/docs/234575
NOTE : If we do not receive your reply within two business days, this post would be marked "assumed answered" and would be moved to "answered questions"pool.