Edit: September 25, 2023 - Added more details to the solution for my issue.
Just wanted to update this so if anyone else is having the same issue hopefully it helps them.
During initial tenant setup I created a couple of retention policies. I thought these would only affect Teams data, but it turns out it also applied to Exchange Online mailboxes. When I tried to remove the Exchange Online license from the user it would give an Exchange error message in admin console and the mailbox would not get removed.
The issue turned out to be caused by holds that were applied to the user mailbox. Specifically these two:
DelayHoldApplied
ReleaseDelayHoldApplied
Both were set to $true.
I removed the retention policies, they probably weren’t configured correct in the first place.
Used the following Powershell command to identify the holds applied to mailboxes:
Get-Mailbox | FL Identity,*HoldApplied*
Used the “Set-Mailbox” command to remove those holds:
Delete the user’s mailbox by removing the Exchange Online license from the user and waited for the mailbox to disappear from the Exchange Online admin center.
Run the following command to wipe out the pre-existing mailbox data. Without doing this, even after the on-prem user is synced Exchange Online will not care that the user has an on-prem mailbox, and will restore the previously deleted cloud mailbox from step 4.
Re-enable the Exchange Online license for the user. After this is done in the users Mail settings you should see a message “This user’s on-premises mailbox hasn’t been migrated to Exchange Online. The Exchange Online mailbox will be available after migration is completed”