AADConnect needs to sync the mailbox enabled ExchangeGUID first - before you apply the license.
So, ensure that value is synced before applying the license.
Are you using AADConnect? It should be doing that by default if you enabled the Exchange Hybrid option
An Exchange Online license was applied to the user before the Exchange GUID got synchronized from on-premises Active Directory. For synchronized accounts, having the Exchange GUID synchronized from on-premises is used to tell Exchange Online that the mailbox hasn’t been migrated yet, and is what allows customers to pre-license accounts prior to migration.