Exchange Online Migration results in Transient error StoragePermanentException

While migrating users from an on-premises Exchange environment to Exchange Online, you could regularly see the error TransientFailure in the Status of a move request. Normally this issue will solve itself, except this time. The move request would not proceed 10%. In the end this move request failed with status FailedMapi. The Underlying error was: Transient error [...]