The security certificate on the server is invalid. Contact your Exchange Server administrator or ISP to install a valid certificate on the server. Support Code: 80072F0D or 0x80072f0d

I had some Windows Mobile device that did not sync anymore. I changed the Certificates on Exchange 2007 and ISA 2006 Servers.

After some investing. The problem was I was missing the GlobalSign Domain Validation CA certificate

After creating the cer file and installed on my PDA active sync works again.

Source:
http://support.microsoft.com/kb/927465

http://support.microsoft.com/kb/915438