The first two mailboxes were moved fine, but when we added more move-requests all requests failed.
The most common error we got was "StalledDueToMailboxLock" and "TransientFailure".
Things we tested first were internal moves. Creating a second Exchange Dbase and moving mailboxes to that Dbase. All moves completed succesfully. My conclusion : Not an Exchange issue but a network issue.
That lead us to our TMG server.
We checked the alerts in TMG and the following error draw my attention.
When opening the alert, you will see that the IP address starts with 157.55 ( in almost all cases ).
These are Microsoft IP adresses, and therefore the moves will not complete successfully because TMG cuts off the request.
We resolved the issue by adding an IP exclusion for Flood Mitigation.
This can be found under the configuration tab, and choosing "general"
Then choosing "Configure Flood Mitigation Settings".
We added an IP exclusion for the range of Microsoft Exchange servers. We added the complete 157.55.x.x range.
Click OK and dont forget to save your TMG configuration.
This had a direct effect on my mailbox moves, they worked!
These settings are the same in ISA of TMG, it's possible that the flood mitigation settings are on another tab, but in general the settings are the same.
Hope this helps in your Office 365 migration.