Exchange logon account fails after its mailbox is moved

[Haddy]

I have two Exchange 2003 servers.  One is on Windows 2000 ("old"), the other on Windows 2003 ("new").  Same domain.  Backup Exec is 2010 running on Windows 2008 R2.
 
The backing up of Exchange mailboxes has always worked with the special logon account created for it ("veritas").  Its mailbox resides on the "old" server.  As part of phasing out Exchange on my "old" server, I am moving all the mailboxes to Exchange on the "new" server including the "veritas" account mailbox.  The administrative group is the same.
 
Once I did that, I went back to my Exchange server backup jobs and ran credential tests against the mailboxes and it now fails with the "Cannot log on to MAPI ..." error.  If I move the mailbox back to the "old" server, the credential test passes.  I've added the "veritas" account to the local administrator group on the "new" server which I think is the only modification I would need to do.
 
Any idea as to why the credential test fails when I move the mailbox and how to fix it?
 
As if things weren't complicated enough, I tried creating an entirely new logon account for the Exchange mailboxes.  This one called "symantec".  It's mailbox resides on the "new" server.  I added it to the local and domain admin groups, made it an Exchange Full Administrator through Delegate Control, logged into the "symantec" mailbox through Outlook Web Access and sent/received an email, everything I'm supposed to do.  If I try using the "symantec" account for my Exchange mailboxes, I get the same MAPI error.  If I then move that "symantec" mailbox to the "old" server, the credential test passes.
 
So there is something with my "new" Exchange server that is causing this problem.

[Haddy · Accepted solution]

I ended up figuring this one out.

It turns out that I needed to modify the permissions of the Mailbox Store on my "new" server (Windows Server 2003).

1. Right-click the Mailbox Store and choose Properties
2. Select the Security Tab
3. Click the Advanced button
4. Click the Add button
5. For the Object Name, type in Domain Admins and click Check Names and OK
6. Scroll to the bottom and put a check mark in Allow for Receive As and Send As and click OK three times

This gives my Exchange logon account (which is a member of the Domain Admins group) abilities that are needed by Backup Exec.

This document contains the only reference I could find for this. http://seer.entsupport.symantec.com/docs/249456.htm