Run the “Windows Azure Active Directory Module for PowerShell” on the machine with dirsync (not sure if you have to download that one or if it's installed with dirsync. If you need to download it, it's here)
Connect-MSOLService get-msoluser get-msoluser -ReturnDeletedUsers | select UserPrincipalName, ObjectId
The second command above shows a list of all deleted users.
To permanently delete one of the results, use the returned ObjectID in above statement in the Remove-MsolUser statement:
Remove-MsolUser -RemoveFromRecycleBin –ObjectId ObjectId -force
To permanently delete all of the users in the recycle bin, run:
Get-MsolUser -ReturnDeletedUsers | Remove-MsolUser –RemoveFromRecycleBin -Force