Thank you for updating on the issue. To isolate the issue, please try the following:
1. Create a new user account using Active Directory Users and Computers. Make the account the member of Domain Admin group and the Local Administrator of the Exchange server.
2. Create new Logon Account in Backup Exec using the same username and password.
Start Backup Exec -Select Tools > Wizards > Logon account wizard -Add new logon account, type in the credential for the new account. -Make this account a common logon account. -Complete the wizard.
3. Delegate this account Full Exchange Administrator rights on the exchange server using System Manager at the Exchange organization level.
4. Create a unique mailbox corresponding to the newly created account. Make sure that the mailbox is not hidden and is visible in the Global Address List.
5. Send some mails to the newly created account.
6. Stop and restart all Backup Exec services. If possible, reboot the server.
7. Reboot the Exchange server. For test purposes, stop/disable Anti-Virus application.
8. We suggest you to enable Restrict Anonymous Support on Backup Exec Server as well as the remote Exchange Server.
http://seer.support.veritas.com/docs/238618.htm
9. Try taking the backup using newly created account and verify the result.