Can you paste the complete values of the send connector you use to send to 365 from on-prem ( removing any domain info)
get-sendconnector <Connector to 365> |FL
Make sure this is set to $true
-CloudServicesMailEnabled $true
Is there a matching inbound connector on the 365 side?
More info: