They can do public-key pinning like Chrome does (for example, they embed the "mail.google.com" public key into Chrome itself, and verify that it's the certificate you're TLS'ing to.