Symptoms
Exchange mailbox creation taks fails with the following error:
Destination host 'EXMBX.provider.net' (#432), IP '10.2.12.29' : Provisioning request failed. Unknown error 0x80131600 [<response><errorContext description="[Unspecified error while trying to mail-enable a mail-disabled object]Offline address book "provider.net/Configuration/Deleted Objects/S0010000 OAL
DEL:e856f50d-be0a-4d5e-b835-f14b96c30475" was not found. Please make sure you have typed it correctly.
Cmdlet='Set-Mailbox'
DomainController='AD.provider.net'
Identity='LDAP://CN=azaza,OU=S0010000,OU=Hosting,DC=provider,DC=net'" code="0x80131600" executeSeqNo="21"><errorSource namespace="Error Provider" procedure="SetError"/><errorSource namespace="SW Managed Exchange" procedure="CheckMailEnabledObject_"/><errorSource namespace="SW Managed Exchange" procedure="CreateMailbox"/></errorContext></response>]
Cause
On Exchange mailbox creation POA searches for an Active Directory Other Well Known Object (OWKO) that points to other objects for the Exchange organization the mailbox belongs to. According to the error output the Offline Address Lists for both subscription's organizations are pointing to Active Directory tombstone which means that these objects have been removed, but for some reasons OWKO still point to them.
Resolution
Please check OWKO for Offline Address Lists for the subscription in question using the KB10014, if the OWKO is not correct it is needed to modify them to point to correct Exchange object using KB10015.