I forgot to mention our Exchange OWA server uses a certificate from the same
CA and Outlook 2K7 happily uses RPC over HTTPS against that so it seems
inconsistent in it's approach to certificate verification.

For what it's worth this is on XPSP2.