When deleting users in the Microsoft Online Portal these deleted users are moved to the Recycle Bin where they will be retained for another 30 days. You can see this when selecting Deleted Users in the Portal:

In the Portal it is not possible to permanently remove users, or purge deleted user accounts. This can only be done using Remote PowerShell. Please note that the Azure Active Directory Module for Windows PowerShell need to be installed. Click here to install this PowerShell module.

To connect to the Azure Active Directory you can use the following commands:

$msolcred = get-credential admin@contoso.onmicrosoft.com
connect-msolservice -credential $msolcred

To retrieve a list of all deleted users in the recycle bin you can use the following command:

Get-MsolUser –ReturnDeletedUsers

To remove all these users you can combine this command with the Remove-MsolUser command:

Get-MsolUser –ReturnDeletedUsers | Remove-MsolUser –RemoveFromRecycleBin –Force

When you check the Deleted Users in the Online Portal you’ll see that it is empty.