The title for this post is a bit incomplete because there wasn't enough space for a full explanation. Here is the scenario I had...
Before setting up hybrid mode for an Exchange 2010 organization, a user account was created in Office 365 with the same UPN as a user account in on-premises. The on-premises domain had been added to Office 365, but directory synchronization was not yet in place. As part of testing, the user account had been give an Office 365 license, which then created an online Exchange mailbox.
When directory synchronization was configured, the on-premises AD account was matched with the existing cloud user. However, the on-premises user has an on-premises mailbox and the cloud user has a cloud mailbox. When viewing the cloud user in Office 365, you could see the mailbox in the cloud.
Because there was an existing cloud mailbox I couldn't move the on-premises mailbox up to Office 365. There was also no way to remove the cloud mailbox to allow the on-premises mailbox to replace it. If the user license was removed, then the cloud mailbox was removed, but came back again when the license was re-added.
To fix this I had to delete the cloud user account and recreate it. To delete the cloud user account, I moved it into an organizational unit that Azure AD Connect was not syncing. Then I purged the user account in Office 365 with the following cmdlet:
Remove-MsolUser -UserPrincipalName user@domain.com -RemoveFromRecycleBin
Finally I moved the user back to an OU that was synchronized. This recreated the cloud user account without a mailbox and the account was identified as having an on-premises mailbox.