We hade same issue, migrate email with bittitan, moved domain from one tenant to another and could not connect with Outlook.
The DNS records was added automatically for the "new" domain so we removed them and added everything manually. May have done something but not convinced.
Ran Sara https://aka.ms/sara and did the Outlook tool. This noticed that there was a problem with Modern authentication and seemed to fix it for the user. But did not fix for all users.
Resolution: Turn off and save Modern authentication, then turn it back on again. This enables the Modern authentication for all accounts on the new domain.