This week I'm performing a new cross tenant mailbox migration.
I have some experience with this kind of migrations, ( it's the third one I'm in charge of ), and with the new procedure, ( will paste the link with the instructions at the end of this article ), an Azure Key Vault is no longer required, so I was very confident and thought that I would no have any issue. But, as sometimes occurs, I was wrong 
The setup was quite easy, and the mail users configuration was like always, so no a big deal.
But now comes the point... Once I launched the migration batch, half of the users started syncing correctly and the ther ones failed, ( neither a MoveRequest was able to start for them ).
Once I checked the errors, I got the same for all the failed ones:
" NotAcceptedDomainException: You can't use the domain because it's not an accepted domain
for your organization ".
Ok. No problem... ( I thought ). I work with Exchange since more than 10 years and this is a common error message. ( Again I was wrong ).
I started to check the mail users, looking for some misspelled domain, missing alias, spaces, etc... Basically, the troubleshooting for this kind of errors. But from my perspective all looked good. So, I decided to reconfigure all the mailusers with a script, launch a delta sync, and resume the failed moverequest. But again, same error for all of them.
Checked again, with PS, from source and target tenant, checked in AD, all the proxy addresses... Nothing, all was correct! Non sense...
Ok. At that point I decid to compare some syncing mail users with some failed ones, looking for anything that could be a pattern. And "voilá"! The syncing users were all licensed in O365... The failed ones not! After assigning a license to the failed ones and resume the MoveRequest, all started to work smoothly.
For sure, I would have saved many hours of work if the error message had been: " The user is not licensed ". But, yeah... It would have been too simple :)
Summarizing, make sure that the mail users have an O365 license before you start the migration batch. And remember, not always the error messages are what they seems to be :)
Cross Tenant Mailbox Migration procedure, ( Preview :(
Cross-tenant mailbox migration - Microsoft 365 Enterprise | Microsoft Docs
