First, I thought it had something to do with our Exchange configuration, but after several days troubleshooting with MS support, I found out it was a network issue.
Unfortunately, we use TMG. And as there is NO documentation about configuring TMG for Exchange 2010 and Office 365 Rich coexistence, it was quite a challenge.
But with some trial and error, I managed to get things working.
First of all, this was the error I got when moving the mailboxes from on-prem to the cloud.
The error is quite generic, and had multiple resolutions according to the community.
Unfortunately, I did not find my resolution on the community.
Because the error is quite generic, I decided to run the command in powershell.
To do this, open a normal powershell window.
We need to connect to Office 365 remote powershell, to do this run the following commands.
Type in your Office 365 admin credentials and run the following.
Then, you need to run the same command as the GUI does, but with minor changes.
Here I use the -identity command instead of the Mailbox Guid.
You notice that powershell gives a much more specific error than the GUI.
As the error has something to do with authentication, I checked the logs from TMG.
In the logs I found the below error.
This indicated there is something wrong with our publishing rules.
After some trial and error, I found out that I needed to change the authentication delegation for the outlook anywhere rule.
I changed the authentication delegation to "No delegation, but client may authenticate directly".
When you select the delegation method No Delegation, but client may authenticate directly, the user's credentials are passed to the destination server without any additional action on the part of TMG Server. The client and the destination server then negotiate the authentication.
Save your TMG / ISA configuration and re-run the move-mailbox command from the remote powershell.
In my case, the mailbox move was succesfull.
You can do a Get-moverequest to show the status of the move.
Another problem solved, but.... certainly not the last :)