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. 
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.
MS Office 365
Windows 10 Pro
Outlook for Microsoft 365 MSO (Version 2303)