Problem

ActiveSync devices, and Outlook clients happily sync against an Exchange 2003 server.

Then you migrate to Exchange 2007.  "Error 0x80072f0d" starts appearing on the devices.  If you publish (via ISA) your RPC directory without HTTPS/SSL encryption, everything works fine.

No matter how you install your CA cert - it doesn't work.  Same error message.

Discussion

The reason behind this is because in Exchange 2007, the Autodiscover service – which is used to find things like free/busy, OOF, Automatic e-mail profile configuration, OAB, etc for Outlook 2007 clients – requires SSL. Therefore, the certificate used needs to have the FQDN of Autodiscover added as a Subject Alternative Name.

As you may know, when you create a certificate there's a 'common name' associated with that certificate...usually in the form of something like "mail.domain.com."

The Subject Alternative Name field is used to add additional DNS names to the certificate. So if it doesn't have an SAN for autodiscover.domain.com it means that it won't validate requests to the Autodiscover service. If you would be using Outlook 2007 clients connecting remotely using RPC/HTTPS and purchasing a 3rd party certificate then you will need to contact your certificate vendor for a certificate that includes the Subject Alternative Name. Instructions for generating a certificate request that can be sent to a 3rd party or Microsoft CA - which includes the SAN for autodiscover is documented as below.

Please note that  the new certificate from your 3rd party Certificate vendor  or Internal CA  should contain the “Subject Alternative Name” (SAN) with the below DNS values.
 
The entries that the “SAN” should contain are as below:
 
DNS Name = Internet Published OWA URL
DNS Name = CAS machine NETBIOS name
DNS Name = CAS machine Full Computer  Name
DNS Name = Internal Domain Name (FQDN )
DNS Name = autodiscover.<InternalDomainName>
DNS Name = autodiscover.<ExternalDomainName>

Please note the first DNS name should always be the Internet Published OWA URL. The order of the other DNS name don’t matter.