In one environment, I noticed various security certificate symptoms that caused problems on a particular Windows 2003 Server x64 Workstation.

• Outlook 2007 gave certificate errors on launch (autodiscover)
• Internet Explorer 8 could not browse internal HTTPS site
• Digitally signed email from others complained about invalid signatures
• I could not digitally sign a new message from Outlook 2007

Some of the errors mentioned included text like "The signature of the certificate cannot be verified" and "The integrity of this certificate cannot be guaranteed. The certificate may be corrupted or may have been altered". I had ripped out all the internal certificates and re-added them.

Looking at one email that came through with a digital signature that did not have any errors, I saw it had a different certification path. The CA was the same, but an intermediate certificate was different and appeared older. Also other newer OS's (aka Server 2008, Windows7) did not seem to have any issues.

I found this MS KB article/hotfix. Once installed and after a reboot, the issue went away.

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

Applications that use the Cryptography API cannot validate an X.509 certificate in Windows Server 2003