We finally found the problem!
Salesforce.com does not support SNI. You must use IP-based SSL.
If you're trying to make an outbound HTTPS request from SFDC to your server which is hosted in some cloud platform (Windows Azure in our case) then chances are you are using SNI for SSL.
SNI allows multiple SSL certificates to be assigned to the same IP address. Modern browsers support it which is why the certificate seems to be installed correctly. Unfortunately, Apex & Outbound Messages do not support it. You must switch your server to use the traditional, more widely supported, and sometimes more expensive IP-based configuration.
We discovered the problem after using OpenSSL to make a request to our site and noticed that our certificate was not being returned. Instead, a certificate for Windows Azure was being returned. This was confusing because other tools and sites such as https://www.digicert.com/help all indicated that our correct certificate was being returned. This is probably because those tools support SNI. Anything that does not support SNI will retrieve an incorrect certificate for the request which is what was causing our Outbound Message to fail.