Recently had a customer with an Exchange 2013 Hybrid config require updating an expired SSL certificate.  When they imported the new certificate and assigned it 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 fix 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