If the Directory Sync connection between an Office 365 and AD account breaks for some reason (AD user is deleted, server corruption etc) it can be tricky to get them reconnected. These steps may help:
1) Use Office 365 Control panel to restore deleted user. It will now be marked as “In Cloud” instead of “Synced with Active Directory”.
2) Use the local AD tools to re-create user if it is missing. Local Exchange tools should be used to create a new mail user with an SMTP address that matches the SMTP address of the Office 365 User.
3) Fire up Powershell and connect to the Office 365 Azure Cloud using the following commands:
Import-Module MSOnline $O365Cred = Get-Credential $O365Session = New-PSSession –ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell -Credential $O365Cred -Authentication Basic -AllowRedirection Import-PSSession $O365Session -AllowClobber Connect-MsolService –Credential $O365Cred
4) Use the following command to delete the ImmutableID from the Office 365 Account where ‘User Principal Name’ is either the name or the email address of the user being reset:
Set-MsolUser -UserPrincipalName 'User Principal Name' -ImmutableId '$null'
5) Wait for, or force, the AD Sync and it should reconnect the accounts.