After deleting a user from Office365 you will notice they remain in the “Deleted Users” list. This can be problematical when trying to sync a user with AD Connect.
To remove permanently you will need to do the following steps in powershell:

1. Connect to your Office 365 in SharePoint Online Management Shell:


2. List all users in the deleted user list:

Get-MsolUser -ReturnDeletedUsers

3. Permanently delete user:

Remove-MsolUser -UserPrincipalName <User@EmailFromList> -RemoveFromRecycleBin