When a user who has been given access to search another user’s email tries to retrieve one of that other user's email messages they get an error.
This can occur if the Exchange server name has been changed.
To correct this issue, remove all instances of the affected user from the Mailbox Manager. This not only includes their mailbox but also removing from the access lists of the other mailboxes that they have been given access to search. Restart the policy service. Recreate the user in the Mailbox Manager and give them access to the other mailboxes that they need to access.