New-MoveRequest is failing for some new on-premises mailboxes with ExchangeOnlineManagement module 2.0.6-Preview7

Question

We are running Azure AD Connect 2.0.28 (yes I know I need to update) and the ExchangeOnlineManagement module 2.0.6-Preview7

We have a scheduled task that will look for any newly-created on-premises Exchange mailboxes and will then move them to Exchange Online via the "New-MoveRequest" command.

For some new mailboxes (not all), the move is failing.

This is the error we see:

PS>TerminatingError(Invoke-WebRequest): "{"error":{"code":"NotFound","message":"Error executing cmdlet","details":[{"code":"Context","target":"","message":"Ex04C125|Microsoft.Exchange.Configuration.Tasks.ManagementObjectNotFoundException|The operation couldn't be performed because 'John.Smith@Company portal .com' couldn't be found. Reason: "}],"innererror":{"message":"Error executing cmdlet","type":"Microsoft.Exchange.Admin.OData.Core.ODataServiceException","stacktrace":" at Microsoft.Exchange.AdminApi.CommandInvocation.CommandInvocation.InvokeCommand(QueryContext queryContext, CmdletInvokeInputType cmdletInvokeInputType)\r\n at Microsoft.Exchange.Admin.OData.Core.PathSegmentToExpressionTranslator.Translate(OperationImportSegment segment)\r\n at Microsoft.Exchange.Admin.OData.Core.QueryContext.ResolveQuery(ODataContext context, Int32 level)\r\n at Microsoft.Exchange.Admin.OData.Core.Handlers.OperationHandler.Process(IODataRequestMessage requestMessage, IODataResponseMessage responseMessage)\r\n at Microsoft.Exchange.Admin.OData.Core.Handlers.RequestHandler.Process(Stream requestStream)","internalexception":{"message":"Exception of type 'Microsoft.Exchange.Management.PSDirectInvoke.DirectInvokeCmdletExecutionException' was thrown.","type":"Microsoft.Exchange.Management.PSDirectInvoke.DirectInvokeCmdletExecutionException","stacktrace":" at Microsoft.Exchange.Management.PSDirectInvoke.PSDirectInvokeCmdletFactory.InvokeCmdletInternal[TCmdlet,TResult](Func1 createCmdlet, Action1 setParameterDelegate, List1 captureAdditionalIO, List1 directInvokeExceptions, Boolean shouldAllowProactiveProxyToReturnRoutingHint)"}}}}"
Write-ErrorMessage : Ex04C125|Microsoft.Exchange.Configuration.Tasks.ManagementObjectNotFoundException|The operation
couldn't be performed because 'John.Smith@Company portal .com' couldn't be found. Reason:
At C:\Users\Admin\AppData\Local\Temp\tmpEXO_qhfppcoq.m4h\tmpEXO_qhfppcoq.m4h.psm1:1110 char:13

• Write-ErrorMessage $ErrorObject $IsFromBatchingRequest
• ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
• CategoryInfo : NotSpecified: (:) [New-MoveRequest], ManagementObjectNotFoundException
• FullyQualifiedErrorId : [Server=ServerRemoved,RequestId=GUIDRemoved,TimeStamp=Thu, 08
  Sep 2022 13:25:08 GMT],Write-ErrorMessage
  Write-ErrorMessage : Ex04C125|Microsoft.Exchange.Configuration.Tasks.ManagementObjectNotFoundException|The operation
  couldn't be performed because 'John.Smith@Company portal .com' couldn't be found. Reason:
  At C:\Users\Admin\AppData\Local\Temp\tmpEXO_qhfppcoq.m4h\tmpEXO_qhfppcoq.m4h.psm1:1110 char:13
• Write-ErrorMessage $ErrorObject $IsFromBatchingRequest
• ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
• CategoryInfo : NotSpecified: (:) [New-MoveRequest], ManagementObjectNotFoundException
• FullyQualifiedErrorId : [Server=ServerRemoved,RequestId=GUIDRemoved, 08 Sep 2022 13:25:08 GMT],Write-ErrorMessage

PS>TerminatingError(Invoke-WebRequest): "{"error":{"code":"NotFound","message":"Error executing cmdlet","details":[{"code":"Context","target":"","message":"|Microsoft.Exchange.Configuration.Tasks.ManagementObjectNotFoundException|No such request exists in the specified index."}],"innererror":{"mess

age":"Error executing cmdlet","type":"Microsoft.Exchange.Admin.OData.Core.ODataServiceException","stacktrace":" at Microsoft.Exchange.AdminApi.CommandInvocation.CommandInvocation.InvokeCommand(QueryContext queryContext, CmdletInvokeInputType cmdletInvokeInputType)\r\n at Microsoft.Exchange.Admin.OData.Core.PathSegmentToExpressionTranslator.Translate(OperationImportSegment segment)\r\n at Microsoft.Exchange.Admin.OData.Core.QueryContext.ResolveQuery(ODataContext context, Int32 level)\r\n at Microsoft.Exchange.Admin.OData.Core.Handlers.OperationHandler.Process(IODataRequestMessage requestMessage, IODataResponseMessage responseMessage)\r\n at Microsoft.Exchange.Admin.OData.Core.Handlers.RequestHandler.Process(Stream requestStream)","internalexception":{"message":"Exception of type 'Microsoft.Exchange.Management.PSDirectInvoke.DirectInvokeCmdletExecutionException' was thrown.","type":"Microsoft.Exchange.Management.PSDirectInvoke.DirectInvokeCmdletExecutionException","stacktrace":" at Microsoft.Exchange.Management.PSDirectInvoke.PSDirectInvokeCmdletFactory.InvokeCmdletInternal[TCmdlet,TResult](Func1 createCmdlet, Action1 setParameterDelegate, List1 captureAdditionalIO, List1 directInvokeExceptions, Boolean shouldAllowProactiveProxyToReturnRoutingHint)"}}}}"

I have verified that the user is synchronized properly via the "Get-MSOLUser" command. Additionally, in Exchange Online PowerShell, the "Get-User" command for one of the mailboxes failing to move returns the user. However, the "Get-Recipient" command does not.

I was able to resolve this issue for 1 user in which I removed them from 365/Azure and then deleted them from the recycle bin.

Initiated an Azure AD Connect sync and a few minutes later the New-MoveRequest command worked.

Deleting users is not a viable workaround for this issue.

Any ideas on the resolution?