Check the Backup Exec Service Account (BESA) credentials.
1. Use a logon account in Backup Exec that is a unique account in Active Directory with an activated mailbox on the Exchange server. A unique name is one that does not exist in the organization as a subset of characters in another mailbox name.
2. Ensure that the BESA has Admin, Domain Admin, and Exchange Organization Admin rights.
3. The BESA should be assigned the Exchange Server Administrators role in Exchange.
4. Verify that the mailbox for BESA is not hidden in the Global Address list.
5. Logon to the Exchange server with the BESA. Obtain additional group membership information by running the following command on the Exchange server: Open a CMD prompt and enter gpresult /z > C:\gpresult.txt.
Try performing a re-direct restore and see if that works