Unable to remove a mailbox not down to litigation hold but down to something called DelayHoldapplied which you can query with this command:
Get-Mailbox server.bear@bear.growl | fl Delay*
DelayHoldApplied : True
DelayReleaseHoldApplied : False
This is a undocumented process that is described as:
A Delay Hold is applied whenever a hold is removed from a mailbox (as in, the mailbox is excluded from an inherited policy or manually removed from an explicitly included policy), and stays in effect for 30 days. This gives administrators the ability to recover data before it is permanently deleted.
However, when troubleshooting holds (such as when you need to perform authorized search-and-destroy operations to remove data from mailboxes with holds applied), the Delay Hold can trip you up.
I was not doing hold troubleshooting, however I did have mailbox that was on-premises that also existed in EXO, which means the mails for this account would end up being delivered to the EXO account not the on-premises account (that can happen in a Hybrid configuration)
With this "DelayHoldApplied" the mailbox remained valid in EXO, so to fix this run these commands to get rid of the mailbox in EXO:
Connect-ExchangeOnline
Get-Mailbox -identity UPN | Select Name,*hold*
Set-Mailbox -identity UPN -removedelayholdapplied
Set-Mailbox -identity UPN -removedelayreleaseholdapplied
Once the command in bold was executed the mailbox updated to this:
Get-Mailbox server.bear@bear.growl | fl Delay*
DelayHoldApplied : False
DelayReleaseHoldApplied : False