Mailflow issue from Exchange On-Prem to Office 365

You are on Exchange Hybrid environment and sending/receiving emails to/from Office 365 via specific Send Connector/ Receive Connector which has TlsCertificateName attribute configured and EOP is doing certificate validation for Inbound/Outbound 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 connectors.
--> Third party certificate is not assigned to the SMTP services.
--> Status of that third party certificate shows "INVALID" or "RevocationCheckFailure".

Please perform the following steps to resolve the issue.

--> Update the TLSCertificateName attribute on the Office 365 SendConnector.

$Cert = Get-ExchangeCertificate -Thumbprint <New Exchange Certificate>
$TLSCert = (‘<I>’+$cert.issuer+'<S>’+$cert.subject)
Set-SendConnector -Identity <Office 365 send Connector> -TLSCertificateName $TLSCert

-->Update the TLSCertificateName attribute on the Exchange On-Premises(Hybrid) Receive Connector which is receiving email from Office 365.

$Cert = Get-ExchangeCertificate -Thumbprint <New Exchange Certificate>
$TLSCert = (‘<I>’+$cert.issuer+'<S>’+$cert.subject)
Set-ReceiveConnector -Identity <Office 365 to On-Prem> -TLSCertificateName $TLSCert

-->Make sure required certificate is assigned to the SMTP service and certificate Status shows VALID.