Normally, user accounts that are deleted within Office 365 sit in "The recycle bin" where they can be recovered if needed. You can't, however, delete users from that gray area within the web GUI. If you wanted to, say, delete and remove the license from a user and create a non-licensed shared mailbox, you're boned without emptying it from the recycle bin first.

Before you start,you'll need Microsoft Online Services Module for Powershell

• http://onlinehelp.microsoft.com/Office365-enterprises/ff652560.aspx
  

To remove a specific user account from the Recycle Bin

1. Connect normally, except add in connecting to the MSO server
   1. $LiveCred = Get-Credential
   2. $Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell/ -Credential $LiveCred -Authentication Basic -AllowRedirection
   3. Import-PSSession $Session
   4. Connect-MSOLService -Credential $LiveCred
2. The ReturnDeletedUsers switch returns accounts found in the recycle bin. To return all:
   1. Get-MSOLUser -ReturnDeletedUsers
3. If you find the account you want to remove, it's a simple cmdlet to do so: where "Email Address" is the upn of the actual account
   1. Remove-MSOLUser -UserPrincipalName "Email Address" -RemoveFromRecycleBin
4. If you're removing an account in order to recreate it, you'll have to wait 5-10 minutes before O365 will allow you to recreate over the deleted account.

If you don't have a problem nuking them all, you can empty all via piping the get to the remove

#Haven't tested this one; have a nagging you may need to fill an array and foreach through all the elements actually.

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