When Office 365 AAD user matching is broken

AAD Sync Error:

Error: AttributeValueMustBeUnique
Correct or remote the duplicate values in your local directory.

Resolution:

There are several things you can attempt and most of them are documented extensively online. So the following solution should work when everything else fails.

If AAD is out of sync and the cloud UPN of most users has changed to onmicrosoft.com, the easiest to get them working is to change each user's UPN manually by connecting to Office 365 PowerShell and running:

Set-MsolUserPrincipalName -UserPrincipalName problem.user@domain.onmicrosoft.com -NewUserPrincipalName problem.user@domain.com

At least that way everyone can still login using their original UPN and previous password, until the sync starts working.

Now you'll have to basically deactivate AAD sync and set it up from scratch.

1. Deactivate AAD Connect for your tenancy using Azure PowerShell:
   Connect-MsolService (login with office 365 admin account)
   Set-MsolDirSyncEnabled -EnableDirsync $False

2. Uninstall AAD Connect from the original server to remove the configuration.

3. At this stage, system will take some time to convert our users to in-cloud. (Please always expect 72 hours normally it takes couple of hours per my experience)

4. Then we will clear the value of immutableID of in-cloud users which is now using sAMAccountName.
   Get-MsolUser -All | Set-MsolUser -ImmutableID “$null”

5. At this point we can enable the AAD Connect for tenant again. (Please always expect 72 hours normally it takes couple of hours per my experience)
   Set-MsolDirSyncEnabled -EnableDirsync $True

6. Then configure AAD Connect with recommended source anchor and synchronization to match user with AD again using SMTP matching automatically. https://support.microsoft.com/en-us/help/2641663/how-to-use-smtp-matching-to-match-on-premises-user-accounts-to-office

7. Start AAD Connect and force a initial synchronization
   Start-ADSyncSyncCycle -PolicyType initial