Yes, it's because of the different source anchor/object ID. You have two ways of remedying this. First, you can use the so-called hard-match method, basically overwriting the sourceanchor value. As you have the value exposed in the error message above, you can simply copy it:
$immutableId = "nCp..."
then set it on the cloud user:
Set-MsolUser -UserPrincipalName ******@domain.com -ImmutableId $immutableId
For the sake of completeness, here's how to calculate the ImmutableId based off of user's ObjectId:
Get-ADUser -Filter * | select UserPrincipalName,ObjectGUID,@{n="ImmutableID";e={[System.Convert]::ToBase64String($_.ObjectGUID.tobytearray())} }
Alternatively, you can use the soft-match method as detailed here: https://support.microsoft.com/en-us/topic/how-to-use-smtp-matching-to-match-on-premises-user-accounts-to-office-365-user-accounts-for-directory-synchronization-75673b94-e1b8-8a9e-c413-ee5a2a1a6a78
For soft-match to work however, you need to first clear the immutableId value. So we're back to running the Set-MsolUser
cmdlet:
Set-MsolUser -UserPrincipalName ******@domain.com -ImmutableId "$null"