TLS Negotiation failed, the certificate doesn't match the host.
After checking multiple sources and tracing numerous email logs and raw headers, we have confirmed the following:
Self-signed certificates are rejected. By default, popular mail servers such as Postfix come with self-signed certificates. At one point, Gmail made a questionable decision of treating these emails as unencrypted. After a short period of contesting, the "CA signed certificate" became a mere recommendation.
Google started enforcing the signing authority without notice. As an operator of a few independent corporate email domains, we were blindsided by this change. As shared on Y Combinator, this is a new and sudden development. What made things worse is the misleading message about a "mismatch" of server certificate. It would have been much clearer if "self-signing" is mentioned anywhere in the error message.
Emails with rejected certificates were attempted. Not all emails failed to go out. There is a chance that the ones that were indeed sent were sent as unencrypted emails. In an effort to keep the encrypted channels pristine, the unencrypted network had to carry the extra load, resulting significant delays within the Gmail network. This certainly did not pan out well with the April 8th outage. During peak hours, we have observed a 65-minute delay between two G Suite accounts.
Turning off TLS is a bad idea. Some forums (links intentionally not included here) suggest turning off TLS and use Port 25 for unencrypted transmission. The irony is as thick as the emails that are piled up at the Gmail gate. At least a self-signed certificate allows encryption. When the cable between a Gmail server and some corporate mail server is tapped into, the email content is not in plain text. Now with a tighter grip, many users will let go of even the most basic security?
CA-Signing with a matching certificate solves the problem. The word "matching" is a source of confusion. We now know that the certificate must be signed with a CA, but for which domain?
Consider this example: abc.com has its MX record pointing to mail.abc.com. In a specific Gmail account, the alias is sending through smtp.abc.com.
In fact, Gmail only cares about the outbound server the very account connects to. If xyz.com is capable of sending emails on abc.com's behalf, Gmail can also connect to xyz.com. The only requirement is that the certificate that's presented by the mail server matches the connecting domain. In this case, one should set up a certificate for smtp.abc.com.
Although the inbound and outbound mail servers can be on different domain or sub domains, they often share the same domain. This makes it easy to test the TLS compliance level online.