In my environment, I have seen all of these. The Access Denied was caused by:
a) Disabled mail-boxes. Had to remove them from the BE job selection list.
b) Deleted mail-boxes that were not completely purged from Exchange. Had to go into Exchange and permanetely remove them.
c) Or, if you are performing a GRT backup of Exchange, and if you have a file path to a specific e-mail message that is longer than 255, you will also get the Access Denied Messages. Had to rename folders in Outlook with a smaller name.
By turning on advanced report logging, you can generally pinpoint exactly what is causing the error message, when the backup job is running.
See the following post for more information:
http://forums.symantec.com/discussions/thread.jspa?messageID=4481044怔