It should have been removed from Azure when it was deleted on-prem, but if not, then use the following steps
If its still licensed, you can remove all the licenses before proceeding.
Remove-MsolUser –UserPrincipalName user@Contoso.com
Remove-MsolUser –UserPrincipalName user@Contoso.com -RemoveFromRecycleBin
The last step will purge it permanently and it cant be recovered.