Today, while migrating to Exchange Online from an on premises 2010 Exchange Server the Exchange console on the onprem client access machine threw the following error when creating a new Remote MoveRequest:

Deserialization fails due to one SerializationException: System.Runtime.Serialization.SerializationException: Unable to find assembly 'Microsoft.Exchange.MailboxReplicationService.Common, Version=15.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35'.
at System.Runtime.Serialization.Formatters.Binary.BinaryAssemblyInfo.GetAssembly()
at System.Runtime.Serialization.Formatters.Binary.ObjectReader.GetType(BinaryAssemblyInfo assemblyInfo, String name)
at System.Runtime.Serialization.Formatters.Binary.ObjectMap..ctor(String objectName, String[] memberNames, BinaryTypeEnum[] binaryTypeEnumA, Object[] typeInformationA, Int32[] memberAssemIds, ObjectReader objectReader, Int32 objectId, BinaryAssemblyInfo assemblyInfo, SizedArray assemIdToAssemblyTable)
at System.Runtime.Serialization.Formatters.Binary.__BinaryParser.ReadObjectWithMapTyped(BinaryObjectWithMapTyped record)
at System.Runtime.Serialization.Formatters.Binary.__BinaryParser.Run()
at System.Runtime.Serialization.Formatters.Binary.ObjectReader.Deserialize(HeaderHandler handler, __BinaryParser serParser, Boolean fCheck, Boolean isCrossAppDomain, IMethodCallMessage methodCallMessage)
at System.Runtime.Serialization.Formatters.Binary.BinaryFormatter.Deserialize(Stream serializationStream, HeaderHandler handler, Boolean fCheck, Boolean isCrossAppDomain, IMethodCallMessage methodCallMessage)
at System.Runtime.Serialization.Formatters.Binary.BinaryFormatter.Deserialize(Stream serializationStream, HeaderHandler handler, Boolean fCheck, IMethodCallMessage methodCallMessage)
at Microsoft.Exchange.Data.SerializationTypeConverter.<>c__DisplayClass3.<DeserializeObject>b__0()

Unable to find assembly 'Microsoft.Exchange.MailboxReplicationService.Common, Version=15.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35'.

This didn’t tell me much, and restarting the Microsoft Exchange Replication Service didn’t help. So I tried Powershell (remote session to Exchange Online):

New-MoveRequest -Remote -Identity "xxx@xxx.nl" -TargetDeliveryDomain "xxx.onmicrosoft.com" -

RemoteHostName "mail.xxxx.nl" -remotecredential $cred

Another error:

The Mailbox Replication Service was unable to connect to the remote server using the credentials provided. Please
check the credentials and try again. The call to 'https://mail.xxx.nl/EWS/mrsproxy.svc' failed. Error details: The
HTTP request is unauthorized with client authentication scheme 'Negotiate'. The authentication header received from
the server was 'Negotiate,NTLM'. --> The remote server returned an error: (401) Unauthorized.. --> The HTTP request is
unauthorized with client authentication scheme 'Negotiate'. The authentication header received from the server was
'Negotiate,NTLM'. --> The remote server returned an error: (401) Unauthorized.
+ CategoryInfo : NotSpecified: (:) [New-MoveRequest], RemotePermanentException
+ FullyQualifiedErrorId : [Server=AMSPR01MB134,RequestId=ac5193f2-0d87-437a-85f1-01da5b8208b6,TimeStamp=25/08/2015
10:16:41] [FailureCategory=Cmdlet-RemotePermanentException] 8C76D656,Microsoft.Exchange.Management.RecipientTasks
.NewMoveRequest
+ PSComputerName : outlook.office365.com

If you run into this issue, there can be two causes:

-your user has email addresses for domains Office 365 does not know

-more likely: the user account you’re using with Get-Credential has the wrong UPN suffix or permissionset