You can’t use the domain because it’s not an accepted domain for your organization

While trying to migrate a mailbox from Exchange 2016 on-premise to Exchange Online using the New-MoveRequest cmdlet it failed and returned this message:

You can’t use the domain because it’s not an accepted domain for your organization

While checking the mailbox properties I realised that this particular user has an additional email address in a different domain (user@ourdomain.fr as well as user@ourdomain.com) and this other domain hadn’t been configured in Office 365 yet.  Once I added the domain and validated it the migration worked as expected.