On-premises users aren’t getting email messages from Office 365 users

It could just be the implementation of the CMDLET and how it is negotiating the connection. Your endpoint is configured with Negotiate, so the client and server should decide if you are using kerberos or NTLM. In your failed attempt it did not detect either correctly, and tried to fall back to Basic Auth - which your server is not configured to support.

NTLM does not support the UPN format, and you did not have a kerberos ticket, so this could be the reason. You generally don't run into this with Windows clients/servers often as most applications seem to take care of reformatting the username reqeust. However if your samAccountName and UPN pre-fix are different then the credentials won't match.

I would be sure your samAccountName and UPN prefixes match on the account. If not, or if they still fail, you should be able to enable basic auth on EWS. This should allow it to fall back on the client side and be accepted on the server side. Since this is an O365 connection, I think we can assume safely your already using HTTPS - which of course is critical if your using Basic Auth as the credentials are sent in plan text.

There is no AD accounts in Exchange 2019 which is related to mailboxes in Exchange Online, in this situation, we could use SMTP match or hard match to associate them. You could refer to the following articles:

How to use SMTP matching to match on-premises user accounts to Office 365 user accounts for directory synchronization https://support.microsoft.com/en-us/kb/2641663 Dirsync soft matching vs hard matching http://tctblgs.azurewebsites.net/dirsync-soft-matching-vs-hard-matching/ ImmutableID Hard Match in Azure AD Connect https://gallery.technet.microsoft.com/office/Immutableid-Hard-Match-in-d3518b08

For the legacy Exchange 2010, the supported way is to uninstall from control pane, if the server is down, you could remove it from ADSI, and please re-run HCW after that.