In the project I’m currently involved, my colleagues are planning to migrate several mailboxes to a new Exchange 2010 platform. This particular issue was encountered when migrating mailboxes from Exchange 2007 (cross-forest) to Exchange 2010. They are currently running several test migrations so we can get an estimate of the amount of mailboxes we can migrate in a given timeframe. Using the New-MoveRequest cmdlet and some PowerShell magic they were processing 100 mailboxes one by one. Oddly a lot of them failed with the following error:

In words:

Failed to reconnect to Active Directory server dc.domain.tld. Make sure the server is available, and that you have used the correct credentials.
    + CategoryInfo          : NotSpecified: (0:Int32) [New-MoveRequest], RemoteTransientException
    + FullyQualifiedErrorId : A46C2901,Microsoft.Exchange.Management.RecipientTasks.NewMoveRequest

After trying the same New-MoveRequest command 5 or 6 times in a row all of a sudden the command finished successfully. Hmm that’s odd! As I’m sitting across my issue radar got activated and I launched google and stumbled upon the following topic: Not able to do a Cross forest Migration between E2k3-E2k7

The solution mentioned over there is to use the <FQDN of domain>\<username> format instead of the <NetBIOS domain name>\<username> when specifying the Remote Credentials. These credentials belong to a user which has permissions on the source mailboxes. Don’t ask for any logical explanation, but it sure did the trick.

For an overview of all supported logon credentials formats, see: KB929272: Interactive logon styles and Key Distribution Center account lookup in Windows Server 2003