Afaik the behavior is as follows: a (mail user) object without a license can have any address you want, i.e. @microsoft.com. Once you apply a license, ExO will "sanitize" any and all addresses that correspond to non-verified domains, regardless of whether assigning the license actually resulted in provisioning a mailbox.
As to how to"fix" this, I'm not 100% sure. One thing to try is to "reprocess" the object after removing the license, you can do this via the Azure AD blade > Users > select the user > Licenses > Reprocess. Another thing is to soft-delete the user object in Azure AD, then recover it immediately, which will not cause any disassociation.