- Make sure there are no network devices between your on-prem org and Exchange Online that may be interfering
- Is the inbound hybrid connector on the Exchange Online configured with the domain set on the cert?
https://learn.microsoft.com/en-us/exchange/certificate-requirements