Objects will age off after 30 days but sometimes you need them gone sooner.

Connect to Office 365:

Get list of users that have been removed:

Get-MsolUser -ReturnDeletedUsers

Remove the user/mailbox in question:

Remove-MsolUser -UserPrincipalName <user email> -RemoveFromRecycleBin