We have been facing this error with users in Riyadh since the Jeddah mail server blow up.
Also, I have been having MAPI error messages when i have been trying to move mailboxes. (I will test this tonight and update).
It turns out that no “Offline Address List” was set up for the Riyadh server. I have now set this to Global Address List. It has tested ok:-
1. Open Exchange System Manager
2. Servername»First Storage Group»Mailbox Store»Properties
3. On the General Tab —Offline Address List
4. Click On Browse»Type in “Default Offline Address List”
5. Clcik on “Check Names” it will resolve to the Default Offline Address List
6. Click OK