AzureAD thinks a user exists when they don't

Question

This is using the latest Powershell and Azure modules. The user was deleted. My question is why can't I recreate them?

PS C:\Users\Administrator> Get-MsolUser -UserPrincipalName 

"[email protected]"
Get-MsolUser : User Not Found.  User: [email protected].
At line:1 char:1
+ Get-MsolUser -UserPrincipalName "[email protected]"
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : OperationStopped: (:) [Get-MsolUser], MicrosoftOnlineException
    + FullyQualifiedErrorId : Microsoft.Online.Administration.Automation.UserNotFoundException,Microsoft.Online.Admini
   stration.Automation.GetUser

PS C:\Users\Administrator> new-msoluser -DisplayName Daniel -UserPrincipalName [email protected] -UsageLocati
on NO -BlockCredential $false -ImmutableId DANIELB620
new-msoluser : Unable to add this user because a user with the user principal name already exists.
At line:1 char:1
+ new-msoluser -DisplayName Daniel -UserPrincipalName bella.daniel@demo ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : OperationStopped: (:) [New-MsolUser], MicrosoftOnlineException
    + FullyQualifiedErrorId : Microsoft.Online.Administration.Automation.UniquenessValidationException,Microsoft.Onlin
   e.Administration.Automation.NewUser

Answer 1

Ah....so AAD doesn't fully delete users. By running Get-MsolUser –ReturnDeletedUsers -All | Remove-MsolUser –RemoveFromRecycleBin –Force I was able to clear them all out and "re-use" the UPN