SYMPTOMS:
Your Exchange server receives extremely delayed (or even does not receive) emails from some domains (e.g. @gmail.com).
In your SMTP logs you see a sequence of 503 and 240 (quit) protocol status message from problematic domains smtp server incoming connections.
CAUSE:
Exchange server advertises TLS as available, and those domains' servers are configured to try STARTTLS first. Your SBS (tipically self-signed) certificate has expired.
RESOLUTION:
When SBS certificate expired you probably ran Internet Connection Wizard in order to renew it. That wizard does NOT replace the certificate stored in exchange smtp server configuration for protected (TLS) communication. This has to be done manually.
In smtp virtual server properties in the connection tab, under protection configuration click "Certificate" button and select "Replace existing certificate". Select the new valid certificate from the list and click next.
Mails start flowing!
