You are on Exchange Hybrid environment and sending emails to Office 365 via specific SendConnector which has TlsCertificateName attribute configured and EOP is doing certificate validation for Inbound SMTP connections.

You might see any of the following errors in the queue/Protocol Logs.
–> 454 4.7.5 The certificate specified in TlsCertificateName of the SendConnector could not be found.
–> TLS negotiation failed with error NoCredentials.
–> „421 4.4.1 Connection timed out.“ Attempted failover to alternate host, but that did not succeed. Either there are no alternate hosts, or delivery failed to all alternate hosts

It may be because of the following issues:
–> You changed the third party SMTP certificate but didn’t update the TlsCertificateName attribute on the send connector.
–> Third party certificate is not assigned to the SMTP services.
–> Status of that third party certificate shows „INVALID“ or „RevocationCheckFailure“.

Please perform the following to resolve the issue.
–> Update the TLSCertificateName attribute on the Office 365 SendConnector.

$cert = Get-ExchangeCertificate -Thumbprint
$TLSCert = (‘<I>’+$cert.issuer+'<S>’+$cert.subject)
Set-SendConnector -Identity -TLSCertificateName $TLSCert
–>Make sure required certificate is assigned to the SMTP service and certificate Status shows VALID.

Quelle: Mailflow issue from Exchange On-Prem to Office 365 – Lalit Bisht Blogs