Moving an Exchange 2010 mailbox with New-MoveRequest fails with: "The discovery mailbox, a hidden default mailbox that is required to search mailboxes, can't be found."

Problem

You’re transitioning from Exchange 2003 or 2010 and with the infrastructure in place, you notice that your mailbox move fails with the following error which is also logged in the application log as event ID 5000:

Failed to save admin audit log for this cmdlet invocation.
Organization: 
Log content:
Subject: Contosonet.com/ContosoNoPolicy/Terence Luk : New-MoveRequest
Body:
Cmdlet Name: New-MoveRequest
Object Modified:
Parameter: TargetDatabase = Mailbox Database 0162106233
Parameter: Identity = Contosonet.com/Users/testuser
Property Modified: UserId = Contosonet.com/Users/testuser
Property Original: UserId =
Caller: Contosonet.com/ContosoNoPolicy/Terence Luk
Succeeded: True
Error: None
Run Date: 2011-07-12T14:13:56
OriginatingServer: ContosoMBX01 (14.01.0218.011)

Error:
Exception thrown during AdminLogProvisioningHandler.Validate: Microsoft.Exchange.Data.Storage.ObjectNotFoundException: The discovery mailbox, a hidden default mailbox that is required to search mailboxes, can't be found. It may have been inadvertently deleted. This mailbox must be re-created before you can search mailboxes.
   at Microsoft.Exchange.Data.Storage.Infoworker.MailboxSearch.MailboxDataProvider.GetDiscoveryMailbox(ADRecipientSession session)
   at Microsoft.Exchange.Management.SystemConfigurationTasks.AdminAuditLogHelper.CheckArbitrationMailboxStatus(OrganizationId organizationId, ADUser& user, ExchangePrincipal& principal, String& errorMessage)

Solution

The reason why Exchange Server 2010 is throwing this error is because there is something wrong with the DiscoverySearchMailbox which is a hidden mailbox that Exchange Server 2010 uses to search through mailboxes and is required when it attempts to move a mailbox.  Unless you’ve moved the object with the associated mailbox to another OU, you should be able to locate the object under the Users container in the domain.  If the object no longer exists, follow the TechNet article here: http://technet.microsoft.com/en-us/library/gg588318.aspx to recreate it with the PowerShell cmdlet.

If the object still exist as shown here:

… the object may have incorrect values for the homeMDB and/or homeMTA attributes.  The following shows the the object’s properties opened in ADSIedit:

Notice how the attribute values are set to <not set>. 

If you’re sure that someone or a process has inadvertently removed the values, you can manually populate the attributes to correct the problem.

The homeMDB attribute is the mailbox database’s distinguished name so if you navigate to:

CN=Databases,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=Contoso,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=Contosonet,DC=com

… you should see a list of mailbox databases that you can choose from.  In the case of this example, there’s only 1 to choose from and it’s the CN=Mailbox Database 0162106233 database:

From here, open up the properties of the mailbox database object, navigate down to the distinguishedName attribute, open the value in the String Attribute Editor and copy it:

From the DiscoverySearchMailbox object’s properties window, paste the value into the homeMDB attribute:

The homeMTA attribute is the mailbox server’s Microsoft MTA’s distinguished name so navigate to:

CN=Microsoft MTA,CN=CONTOSOMBX01,CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=Contoso,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=Contosonet,DC=com

… and perform the same action as you did for the homeMDB attribute by opening up the properties of the Microsoft MTA object, navigate down to the distinguishedName attribute, open the value in the String Attribute Editor and copy it:

From the DiscoverySearchMailbox object’s properties window, paste the value into the homeMTA attribute:

Once these 2 attributes have their values populated with the appropriate values, you should now be able to move mailboxes.