Can't add Office 365 account to Outlook after domain migration to new Office 365 Tenant

Issue

After migrating a domain to a new Microsoft Office 365 Tenant it is no longer possible to re-add email accounts to Outlook on PCs where Outlook was previously configured with the same accounts on the old tenant. The issue was a local Outlook Autodiscover or Credential caching issue. Everything was working fine on the web, mobile devices, and Outlook on PCs where user accounts had never been configured with this Office 365 domain.

The Outlook email account setup wizard, would try to discover Office 365 server settings for a minute or two, and then without ever prompting for user credentials, show the following error:

Something went wrong and Outlook couldn't set up your account. Please try again. If the problem continues, contact your email administrator.

 On some computers, a password prompt would appear, however after entering the correct password, the following error would pop up:

Error. Something went wrong. [1001]

Resolution

The issue was resolved by removing the affected Microsoft Account(s) from MS Office and Windows.

• Open Microsoft Word.
• Click on the username in the top bar
• Click on the three dots next to every affected account and click Sign Out.
  
• If they are present, also remove the affected accounts from Windows Settings > Access work or school.
• Reboot the computer and try adding the account(s) to Outlook again.

Below are some other troubleshooting steps I tried. In this particular case, most of them didn't help, but I'm leaving it here for future reference. 

• Create a new Outlook profile.
• Delete all Microsoft cached credentials from Windows Credential Manager.
• Flush DNS cache.
• Wait 48 hours.
• MS suggested Registry changes to ignore certain Autodiscover methods (HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Outlook\AutoDiscover)
• Delete all Identities related to the domain in question from Registry (HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Common\Identity\Identities)
• Delete all registry entries related to the domain in question.
• Reinstall MS Office.
• Completely wipe MS Office using the Microsoft Office removal tool and reinstall from scratch.
• Creating a completely new Windows user account. This actually always resolves the issue but is way too disruptive for users.
• When adding a new account in Outlook, don't use the primary Office 365 domain, i.e. This email address is being protected from spambots. You need JavaScript enabled to view it.. Instead, use This email address is being protected from spambots. You need JavaScript enabled to view it. (.onmicrosoft.com domain is automatically assigned on new Office 365 tenant creation. When the Microsoft login prompts appear, use the correct email address and password for the user account (This email address is being protected from spambots. You need JavaScript enabled to view it.). This worked in most cases, but was still failing on some computers.

April 2023
MS Office 365
Windows 10 Pro
Outlook for Microsoft 365 MSO (Version 2303)