If you have a conflict in directory settings between Microsoft 365 and your on premise location use the next procedure to solve this
Check if the affected mailbox in Exchange Online is an usermailbox
get-recipient user | fl recipient*
If not already, disable the user account in the on-premise environment.
Wait (or force) until the changes replicate to Microsoft 365. Once it is synced, enable the on-premise object as an remote user mailbox
Enable-RemoteMailbox user -RemoteRoutingAddress firstname.lastname@example.org
Wait (or force) until the sync to Microsoft 365 has been completed and then check the user. The error message should be gone and a license can be added