We have seen similar errors before when the account used for backup does not have sufficient permissions. As of Exchange 2010 SP1 the required permissions seem to have changed from the Microsoft side.
To fix this we have gotten the following instructions from Microsoft. Can you please try to run the following powershell command
get-mailboxdatabase | add-adpermission -user <serviceaccount> -ExtendedRights Receive-As
Also, in ADSIEdit on the domain controller, make sure that this user is a member of the Organization Management group (under Exchange Service Groups) and that the Organization Management group has Receive-As permissions on the organization (sometimes this is marked as Deny by default).Then make sure that the Organization Management group has full control at this level.
If you then run the effective permissions for this group, it should have Full Control, All extended rights , send as, receive as rights
Here is a MS KB with some of this information included
Wearer of Many Hats