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:
3. Permanently delete user:
Remove-MsolUser -UserPrincipalName <User@EmailFromList> -RemoveFromRecycleBin