Deleting users in O365 is pretty easy, you just run:
Remove-MsolUser -UserPrincipalName user@contoso.com
This is pretty straight forward but when you delete a user it goes into the Recycle Bin for 30 days before it's purged. This is great since you can easily restore a user but what if you have a new user with the same name, or you needed to remove and re-add a user?
Once you delete a user you cannot use the same UPN until you purge the deleted account from the recycle bin. Luckily this is a very simple process. All you need to do is to run the remove ommand with the -RemoveFromRecycleBin switch:
Remove-MsolUser -UserPrincipalName user@contoso.com -RemoveFromRecycleBin
To see what users are in the Recycle Bin run:
Get-MsolUser -ReturnDeletedUsers -All
Combining the two you can remove all of the users in the recycle bin by running:
Get-MsolUser -ReturnDeletedUsers -All | Remove-MsolUser -RemoveFromRecycleBin
Nice simple and easy. Happy Purging!