AD Connect - User is synchronized as contact, not mailbox in Exchange Office 365

We recently set up AD Connect for an Active Directory that have previously been synchronized with a different Office 365 tenant. The company was merging with another company and wanted to consolidate on a single Office 365 tenant. Setup went fine and all users were synchronized, but a subset of users were synchronized as mail contacts, and did not get a mailbox provisioned despite being licensed correctly. When we checked Mail Setting on the user object in Microsoft Office 365 Admin Center we got a warning: The user mailbox haven’t been migrated yet.

After quite a bit of research we finally determined that all the offending users still had the Exchange attribute msExchMailboxGuid set in the local Active Directory forest. Having this attribute set made Exchange Online assume that the user still had a mailbox on-premise and that the mailbox would be migrated later.

To fix the problem all we had to do was clear the msExchMailboxGuid. But that too has a built in challenge as no msexch attributes are retrieved by default when you do Get-ADUser. This is how we solved it:

Step 1: Clear attributes

# Get any user with the MSExchMailBoxGuid attribute set
# Make sure you user -Searchbase, or the property will NOT be returned
$Users = Get-ADUser -Filter * -SearchBase "OU=Path_to_OU_with_users,DC=company,DC=com" -Properties msexchmailboxguid | Where {($_.MSExchMailBoxGuid)}

# Clear MSExchMailBoxGuid and the remote recipient type
$users | Set-AdUser -Clear msexchmailboxguid, msexchremoterecipienttype

# Verify that the attribute has been cleared
Get-ADUser -Filter * -SearchBase "OU=Path_to_OU_with_users,DC=company,DC=com" -Properties msexchmailboxguid | Where {($_.MSExchMailBoxGuid)}

Step 2: Re-apply Exchange license

Finally we removed, waited and re-applied the Exchange Online license for all the offending users. Upon re-apply all users had a mailbox provisioned.