You have Directory Synchronization configured in your domain and on occasion you need to delete a synced user in AD then recreate the account.
Here are the steps required in order to enable successful synchronization of the recreated AD account to Office 365.
Delete the user account from AD and perform a sync in order to also remove the user from O365. The cloud account will move to the Deleted users area in O365
In Office365 restore the user from “Deleted Users” area. After it has been restored the user will show up as “in cloud” vs. “synced with Active Directory”
Recreate the account in AD. Ensure that you have filled in the Email section and the Proxy Address for Primary mail account via user object properties and Attribute Editor tab.
Now for the nifty part…Hard Matching using the AD user ObjectGuid
Open the AD user object properties and Attribute Editor tab. Search for Distinguished name and copy the path.
ldifde -d "CN=Someone,OU=Users,DC=someplace,DC=com" -f c:\User.txt
Open the text file you created in Step 4 and copy the user’s ObjectGUID EG: 5WyOPyLejk2wiSyVaLQSGw==
Open PowerShell and update the Cloud users ImmutableID with the ObjectGuid of the AD domain user you copied in Step 5
Set-MsolUser –UserPrincipalName email@example.com -ImmutableId "5WyOPyLejk2wiSyVaLQSGw==”
In PowerShell check that the new ImmutableID has been applied
Get-MsolUser –UserPrincipalName firstname.lastname@example.org | FT name,ImmutableID
Run a synchronization and confirm successful sync. The cloud user will again become “synced with Active Directory”