If you have had to delete Office 365 users either using the Office 365 Administration Portal or PowerShell (For instance, you can use a PowerShell script like the following one: How to remove remove several Office 365 users in bulk!), you have to take into account that deleted users are not definitively removed. Deleted users are sent to the users’ recycle bin. Therefore, if you want to delete definitively these users, I recommend you to read the following article: http://o365info.com/soft-delete-office-365-recycle-bin/. As you can see in the article:
If you execute in the PowerShell command line the cmdlet Get-MsolUser –ReturnDeletedUsers, you will the list of all the deleted users that are currently in users’ the recycle bin.
In order to definitively delete the users from the users’ recycle bin, you have to execute the following PowerShell sequence: Get-MsolUser -ReturnDeletedUsers | Remove-MsolUser -RemoveFromRecycleBin –Force. Once you have execute the sequence, simply review the users have been deleted definitively.