Recently experienced an issue with an Exchange 2013 Hybrid configuration which required updating an expired SSL certificate. When I imported the new certificate and assigned it to the SMTP services, mail flow from on-premises to Office 365 stopped.
This was because the on-premises send connector to Office 365 was still configured to look for that expired certificate (which had also been deleted already).
The solution was to perform the following.
1. Open Exchange Management Shell on the on-premises Exchange server
2. Run Get-ExchangeCertificate, and note the Thumbprint of the correct certificate to be used.
3. Run $cert = Get-ExchangeCertificate -Thumbprint <thumbprint>
4. Set a new variable and assign it the concatenated values of the Issuer and Subject values of the certificate (must also include <I> and <S> before each field): $TLSCert = (‘<I>’+$cert.issuer+'<S>’+$cert.subject)
5. Update the send connector with the new values Set-SendConnector -Identity “Send Connector Name” -TLSCertificateName $TLSCert
After completing this, any queued mail destined for the Office 365 tenant should begin flowing.
Note. May need to restart transport service if email flows still fails following step 5.