I recently was having trouble with BackupEXEC 8.6 and my problem seems to be a very common problem.  This is what I kept seeing in my Job Logs:

     Unable to attach to \\MACHINE_NAME\Microsoft Exchange Mailboxes.
     Access is denied.

Basically to be able to backup and restore individual Exchange Mailboxes the BackupEXEC Service account needs to be able to have access to all of those mailboxes via MAPI..  If you did not setup this service account during the initial install here is how to do it:

  1. Create the account in Active Directory Users and Computers.  NOTE: The first five characters in the account name can not match that of any current/previous account or mailbox.  ANOTHER NOTE: DO NOT HIDE THIS ACCOUNT FROM EXCHANGE ADDRESS LISTS!..credit for this note goes to John 
  2. Join the account to the Administrators group of the domain.
  3. Open up “Exchange System Manager“ and drill down to the Exchange Server that your mailbox is located on.  Right click the server name, select properties and then click on the “Security“ tab.  Add the account you just created and give it Full Control.
  4. Go into Control Panel and open up the Services app.  Double click on all of your Backup EXEC services and have them logon as the service account you created.  You will be told at some point during this that the machine is granting the service the right to logon as a service.  Obviously this is exactly what you want :)
  5. Once you've done this re-start all the Backup EXEC services.
  6. Now open up the Domain Controller Security Policy console and drill down like this: Security Settings --> Local Policies --> User Rights Assignment. Double click “Log on locally“ and add the account you created in step 1.
  7. Now logoff and log back on with the account you created in step 1 and run Backup EXEC.  In case you don't have an icon handy with this account the defalt for the EXE is:

    C:\Program Files\VERITAS\Backup Exec\NT\bkupexec.exe
  8. Select the Backup Selections tab and you should be able to see all the mailboxes you wish to see.

By the way, if anyone reading this knows of a good way to keep the account out of the exchange address lists please take a moment to share :)