Symptoms

The error is reported during backup ( Exchange emails backup sets ) or when trying to expand a certain mailbox that is to be included in the backup selection while editing the intended emails backup set in DS-User.

Cause

a) The DS-Message Level Restore service account does not have a mailbox.
b) The DS-Message Level Restore service account does not have granted appropriate permissions to access the mailbox.
c) MAPI is disabled for a user mailbox (in this scenario only a certain mailbox reports the error).
d) the emails backup set protects an Exchange 2013 and the mailbox reporting the error belongs to a user from another domain or system mailboxes like Health and Migration mailboxes have been added to the backup items list.
e) The registry key RPCHTTPProxyMap_DSMLR is set incorrectly (Exchange 2013).

Workaround

a) Ensure the DS-MLR service account is a domain user that has a mailbox. This user must also belong to the local Administrators group on the DS-MLR computer and to Exchange Organization Management group.

b) Grant the Receive-As permission to DS-Message Level Restore service account on the intended mailbox ( the permissions can be updated at storage group or mailbox database level so that all mailboxes within can be accessed by DS-Message Level Restore service account ). Full Access or Receive As permissions aren't granted until the Microsoft Exchange Information Store service caches the permissions and updates the cache. To grant the permissions immediately, stop and then start the Microsoft Exchange Information Store service. When protecting Exchange 2013 and one or several new mailboxes are created (under a mailbox database already added to the backup items list), the following command must be run again from Exchange Management Shell:
Get-Mailbox | Add-MailboxPermission -User "your_domain\ds-mlr-service-account" -AccessRights FullAccess
replace in the command from above the string your_domain\ds-mlr-service-account with the actual values from the Exchange to be backed up in your environment.

c) Enable MAPI for the user mailbox reporting the errors:
- In Exchange Management Console expand the tree in the left pane and navigate to Recipient Configuration > Mailbox, in the right pane the list of mailboxes is displayed;
- highlight the intended mailbox, right click > properties > Mailbox Features; - highlight "MAPI" and click on "enable", then save the changes.

d) Follow the instructions available in dsuser.pdf document, "DS-MLR with Microsoft Exchange Server 2013 - Additional Configurations Required" section and specify all needed domains ( separated by comma ) when setting the RPCHTTPProxyMap_DSMLR registry key, for example:
dom1.net,dom2.org,dom3.com=https://mail.dom1.net,ntlm,ntlm,false
alternatively the "*" can be used for such scenario, for example:
*=https://mail.dom1.net,ntlm,ntlm,false
The Health and Migration mailboxes are system mailboxes that can be excluded from the backup items list, if these mailboxes are intended to be backed up, the DS-MLR service account must be granted permissions to access them, the Power Shell cmd-lets below will grant permissions to Health and Migration system mailboxes:
Get-Mailbox -Monitoring | Add-MailboxPermission -User "Domain\UserName" -AccessRights FullAccess
Get-Mailbox -Arbitration | Add-MailboxPermission -User "Domain\UserName" -AccessRights FullAccess

e) the last switch of the registry key RPCHTTPProxyMap_DSMLR was set to "true" instead of "false"

f) Microsoft KB 195849.