I have seen a lot of entries on how to get backup working with Backup Exec and Exchange, but I'm concerned since it worked on install, but now shows the "...failed to access "\\Exchange\Microsoft Exchange Mailboxes." Access is denied" error described in the knowledge base and forums.
A consultant installed our copy of Backup Exec as an evaluation, and made the connection to our Exchange server. It worked, but the evaluation expired and it stopped working before we fully implemented a strategy (and we severed ties with our consultant). Then we purchased licenses and got it working. Backup of Exchange worked perfectly, but "failed", because it could not access some specific mailboxes--however, at that point we were not actually using Exchange. Backup Exec is installed on our Windows BDC, and it is set up to use the domain administrator account to access Exchange.
Just about the time we started actually using Exchange, the Job Monitor started showing jobs failing due to being unable to attach to Microsoft Exchange mailboxes and public folders. We also had some system resources on the Exchange server being backed up, and that part continues to work. We seem to have made some adjustment of permissions in Exchange to get public folders working to our satisfaction, and it was about then that backup started failing, but it is trying to access the Exchange folders as domain administrator, so we should have full access to everything.