Had a similar problem with Yahoo... Implemented domain keys and signed all my outbound mail and it fixed the problem.
I ran into this a couple years ago... Bluecoat has a proxy server with a SSL hardware decode card that will spoof SSL certs on the fly. If you are a school/government organization than just push the CA Root cert to all the clients that you used to sign to the cert on the Bluecoat and poof! Instant on demand certificates for all the websites on the internet. You get to be the monkey in the middle and do all the content analysis via ICAP or other means easy peasy. No reason to block it.