O365 Sign in error – AADSTS51004: The user account *** does not exist in the *** directory | O365 Hard match

We had a user who returned to the company and he wanted to have the same AD account and email address. The AD account was restored by the IAM team which somehow populated the Exchange attributes in the on-premises Exchange 2013 and it was displayed as a remote user mailbox as expected in an Exchange Hybrid environment. We could see the mailbox in Exchange Online with all the data as he had left it and did not suspect any issues. The user side IT team started having issues while setting up Outlook for the user and started getting the below error both while configuring Outlook and trying to login to OWA.

Upon checking the mailbox status in Office 365/Azure AD we noticed that the user mailbox is not synced with on-premises Active Directory and is currently acting as a cloud only account. Since our domain is also federated the user authentication seemed to have been failing due to the Sync issue.

To try soft match (or smtp matching) was not an option as the UPN/SMTP address was the same both on-premises and on cloud. The Exchange guid was same in both these forests as well. Next option was to perform a hard match (using ImmutableID). More information on Soft-match/Hard-match can be found here. A good read on ImmutableID can be found here.

Steps to perform hard-match:-

1) Export all the mailbox information from both forests ie, on-premises and cloud for later reference. Take backup of data if required for safer side.

2) In the on-premises side launch powershell window on a server where you have AD management tools installed and run

Import-Module ActiveDirectory.

3) Now find the ObjectGUID of the user account by running the command

Get-ADUser -Identity “user logon name” -Server “domain controller name”

4) Convert the Active Directory ObjectGUID value to Base64 value. The term Base64 is also called SourceAnchor/ImmutableID. This can be achieved many ways for eg: through PowerShell script, 3rd party applications etc. The simplest method is to use this website https://toolslick.com/conversion/data/guid.

5) Connect to Azure Active Directory to update the new ImmuatbleID. First, import the MSOnline module by running

Import-Module MSOnline.

Then run

Connect-MSOLService

and provide your Office 365 admin credentials. Now execute the below command to update the ImmutableID that was converted in step 4.

Set-MsolUser -UserPrincipalName user@contoso.com -ImmutableId **************==

Then either manually run a delta sync on your Azure AD Connect server or wait for the scheduled sync cycle to complete.

For users having a federated domain might get an error like below while running the above Set-MsolUser command:

This issue is discussed here. The solution is to temporarily change the UserPrincipalName to the default onmicrosoft.com domain by running the command:

Set-MsolUserPrincipalName -UserPrincipalName user@contoso.com -NewUserPrincipalName user@contoso.onmicrosoft.com

After the new ImmutableID is updated change the UPN back to the old one. Now wait for the AD Sync to take place. After which the on-premises account will properly sync to the cloud account. You can verify this from Azure Active Directory that the source of the object is Windows Server AD instead of Azure Active Dirctory and the Directory Sync status is showing as enabled.