So thats the question.
If they need that mailbox, then you can't remove the license and purge the user unless you move the mailbox back on-prem, then remove all the licenses and purge from Azure and resync.
I tested this and this works every time using msolservice module:
Change the values on-prem. Make the primary SMTP address and UPN match. Set the alias/mailnickname as required so it will be
mailnick@keyman .onmicrosoft.com
Then:
connect-msolervice
remove-MsolUser -UserPrincipalName SAM@domain.com
remove-MsolUser -UserPrincipalName SAM@domain.com -RemoveFromRecycleBin
Resync and it should be as you want it.
However -as I said, ONLY do this if you do not need the mailbox or any existing data in the current Azure account since you wont be able to recover it from Azure once you remove it from the Recycle Bin