Azure AD Sign in issue: “The account might not exist or it might not be synchronized"

[Unnie]

Scenario:

We have Azure AD tenant set up with user provisioning and federated authentication done via Okta. So, Okta was synchronizing users to Azure AD. 

Now, we installed Azure AD Connect and switched off Okta based user provisioning (Still keeping Okta for federated authentication). We have successfully matched existing users in Azure AD to their AD objects using hard matching based on ObjectGuid. The Azure AD connect based sync was run on all users and it worked for all except 2 users. These users had a mismatch between Azure AD immutableId and ObjectGuid in AD. Then we got sync errors for these 2  users and Azure AD created duplicate account for them with email format as : username-<somenumber>@<tenant>.onmicrosoft.com 

We have corrected those user's immutableId by running PowerShell commands to change the immutableId. Once, the immmutableId of those users were corrected the sync was run again and Azure AD connect now properly matches the Azure AD user with their correct AD object (we tested by changing some irrelevant Ad attributes and they are properly propagated). 

But, when the user tries to login they are first redirected to Okta for login and after Okta login, the tokens are forwarded to Azure AD and user get below error from Azure AD login page:

“The account might not exist or it might not be synchronized. Contact your administrator to add or synchronize the account"

We do not have any major services provisioned in M 365 yet, so can live with user's Azure AD account being recreated. 

Some additional things tested out, but all leads to same sign in behavior:

1. Change the immutable ID of the Azure AD account to match AD object and run sync =  All props are synced but login failure.
2. Delete the existing Azure AD account and run sync to create new account = New Azure AD account created but login fails as before.
3. Create a cloud account, changed the immutable Id to match the AD objectGuid, changed the UPN to match the AD object email, run sync =  The cloud account gets synced to AD object and properties are updated, but login fails

The issue is only for the 2 user account which had this sync error in the beginning, for all other users login is working properly.

Any ideas or pointers to check. What are we missing here?

[#2]

@Unnie 

Because you were using Okta [and Okta requires federation with Azure], are you using ADFS for federation with AD? IF so the issue may be with the Office 365 Relying Party Trust claim rule. I know that when I was working with a customer in helping them with their Okta issues, ADFS and Office 365 I needed to rewrite that to get it to work the way I wanted. I don't remember the details, but it had something to so with the samaccountname matching the beginning of the UPN.

[#3]

Okta authentication is working for the 2 users, but post authentication hen the users are returned to Azure AD page, they get this error. Also, for all other users who did not have any Azure AD Connect sync error during setup, federated authentication via Okta is working properly.