After deleting a user in Office 365, their account is moved to a 'recycle bin' for 30 days. This allows the user account to be easily recovered. This can often cause issues when attempting to recreate a mailbox while a hybrid configuration is in place.
To permanently delete the user within Office 365, first delete the user in the Office 365 Admin Portal or using Powershell. Then, connect to your Azure Active Directory environment with Powershell using the "Connect-MsolService" cmdlet.
To see a list of user accounts currently in the recycle bin, run this cmdlet:
Then, to permanently delete all accounts in the recycle bin, run this cmdlet:
To remove a specific user, run this cmdlet: