Error AADSTS50020 - User account from identity provider does not exist in tenant

Although this error can be caused by several issues, I ran into a very specific scenario today that I could not get any information on. We had just migrated a client from on-premise Exchange 2016 to O365 Hybrid with coexistence. Everything was working as expected with the exception of a single user system outside of the network which could not setup an email account in Outlook 365 after migrating their mailbox to the cloud. When we attempted to connect the account to Outlook we would receive the following error after MFA authentication "AADSTS50020: User account ‘user@domain.com’ from identity provider {IdentityProviderURL} does not exist in tenant {ResourceTenantName}."

After testing we found that the issue was isolated to one particular user profile as logging into a different user account on the PC would allow us to setup the same email account in Outlook without issue.

The typical fixes for similar issues such as removing cached credentials in credential manager did not provide any resolution.

We did eventually find a solution by performing the following:

Step 1:

• Close Outlook

• Open Control Panel > Mail and click profiles

• Delete all Outlook profiles then navigate to C:\Users\user\AppData\Local\Microsoft\ and rename the Outlook folder to Outlook.old (this folder will be recreated on launch).

• Open Outlook and attempt to connect the mailbox.

If it works then you are finished! If not, delete the profile Outlook created and continue to step 2 below:

Step 2:

• Verify or create / edit the following registry entries:

[HKEY_CURRENT_USER\SOFTWARE\Microsoft\Office\16.0\Outlook\AutoDiscover\RedirectServers]
"autodiscover-s.outlook.com"=hex(0):
"autodiscover-s.partner.outlook.cn"=hex(0):
"autodiscover-s.outlook.de"=hex(0):
"autodiscover-s.office365.us"=hex(0):
"autodiscover.hotmail.com"=hex(0):

[HKEY_CURRENT_USER\SOFTWARE\Microsoft\Office\16.0\Outlook\AutoDiscover]
"PreferLocalXML"=dword:00000000
"ExcludeHttpRedirect"=dword:00000000
"ExcludeHttpsAutodiscoverDomain"=dword:00000001
"ExcludeHttpsRootDomain"=dword:00000001
"ExcludeScpLookup"=dword:00000001
"ExcludeSrvRecord"=dword:00000001
"ExcludeExplicitO365Endpoint"=dword:00000000

• Reboot the PC

After reboot, connecting to the account should work without issue.