It is tricky to get the mailbox backups working, but it can be done, heres the instructions I followed which are from Veritas.
Please ensure that the Exchange Administrator tools are installed on the Backup server, and have the same service pack as the Exchange 5.5 server.
Please ensure that there is a unique mailbox attached to the account which controls the Backup Exec services. This account must not share the first 5 letters of it's name with any other mailbox.
Using Exchange Administrator:
Go to Tools/Options/Permissions.
Tick the following boxes: Show permissions page for all objects, display rights for roles on permissions page, try to find matching windows NT account.
At the site level grant the Backup Service account (using file/properties/permissions):
Permission Admin role
Send as rights
Mailbox owner rights
At the server level grant the Backup Service account:
Permission admin role
At the Recipient level grant the unique mailbox for the backup exec service account:
Permissions Admin role
Send as rights
Mailbox owner rights
Ensure that the mailbox is not hidden, and test it by sending an email to it and reading the email (you may need to create a profile)
If this does not resolve the issue:
Stop the 7 Backup Exec services
Copy the Mapi32.dll file from \program files\common files\system\mapi\103*\NT to \program files\VERITAS\backup exec\NT directory.
Find the Bewinui.uni file in the \program files\VERITAS\backup exec\NT\data folder and rename it to bewinui.old.
Start the services and try a backup.
If it still doesn't work, search the local computer for copies of mapi32.dll, you may find one in WINNT\SYSTEM32. Copy this one into \program files\VERITAS\backup exec\NT directory.