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.

disable-mailbox user

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 [email protected]

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