The Scenario
The existing environment consisted of a CCR cluster and a pair of CAS/Hub servers in a WNLB cluster. All servers are physical and the OS was Windows 2003 Server 64-bit. The existing certificates had a whole slew of names that were not needed and I told the client that we would be reducing the number of names on the certificate to 3 – AutoDiscover, Mail and Legacy. This would save them money in the long run (previous certificate could hold up to 10 names) as well as remove names that were no longer supported (internal host names – see here).
For migrations with a lot of mailboxes, I like to plan out a coexistence plan where the clients (Outlook, OWA, ActiveSync) will connect to Exchange 2013 and redirect to Exchange 2007 as needed. This way mailboxes can be moved over time and both systems can be used while we are in transition. This particular client had 1100 mailboxes, making coexistence necessary. I planned all the steps out, had Firewall changes ready and approved as well as all the changes to Exchange 2007/2013 lined up and approved as well. On a week night we switched the flow for HTTP/HTTPS to Exchange 2013 internally (DNS) and externally (NAT). We also changed URLs and changed out the old certificates on the Exchange 2007 servers.
After the changes were made we tested Outlook and OWA to make sure redirection was working. Outlook and OWA worked as expected with our test group. We were able to get to Legacy.domain.com for the Exchange 2007 mailboxes and mail.domain.com for Exchange 2013 mailboxes via OWA. Outlook also connected to either server depending on the mailbox location.
The next morning we checked with our user base and heard that several users were getting pop-ups in their Outlook 2010 client (all users used Outlook 2010).

Why was Outlook complaining about the certificate? There were two Exchange 2007 CAS/Hub servers and both had the same certificate installed the same way and enabled the same way (via PowerShell). Both servers had the certificate applied to the correct services. Also, the URLs had all been changes on Exchange 2007 to Legacy.Domain.Com. This name was on the certificate. My first step was to check the Exchange Certificates installed on the server to see what the Status was. On the first server, which no pop-up was occurring, the certificate status was ‘Valid’:
get-exchangecertificate |fl

Now, I checked the second CAS/Hub server, the one that the prompt was for and I noticed the status of the Exchange certificate was ‘Invalid’:

Two different servers, same certificate, different results. What could be going on here? Next step was to pull up the MMC for Certificates and examine the certificate itself. I do this to see if there are issues with the certificate itself or with the certificate change (in case of a Certificate Revocation List (CRL) issue).
When I opened the new certificate on the server that showed Invalid, I noticed that the entire certificate chain (two Trusted roots and the main certificate itself) were all red. The error message was “The integrity of this certificate cannot be guaranteed. The certificate may be corrupted or may have been altered.” and that the digital signature was invalid. I did a bit of digging and remember something about older servers and newer certificates causing issues. So I checked the list of hotfixes on the server to see what was missing. Maybe one was patched at a different level than the other.
Checking for the update required me to check from one of the Exchange 2013 servers as Windows 2003 and Exchange 2007 run PowerShell 1.0 which does not have the ‘get-hotfix’ command needed to check this quickly.
I ran the command on both the ‘good’ and the ‘bad’ CAS server:


I then copied the results (ignoring the ‘File1’ results) into an Excel spreadsheet. I noticed one update was indeed missing on the ‘bad’ server:

If you were to go to the KB article’s website, you would see the description matches the issue we were having:
“In Microsoft Windows Server 2003, applications that use the Cryptography API (CAPI) cannot validate an X.509 certificate. This problem occurs if the certificate is secured by the Secure Hash Algorithm 2 (SHA2) family of hashing algorithms. Applications may not work as expected if they require the SHA2 family of hashing algorithms.
Additionally, when you evaluate a certificate that uses the SHA2 family of hashing algorithms, you may receive the following message:
The integrity of this certificate cannot be guaranteed. The certificate may be corrupted or may have been altered.”
I wanted to double check the Algorithm used to make sure it matched the SHA2 family of certificates, however, the Algorithm looked incorrect:

The algorithm displayed as ‘1.2.840.113549.1.1.11’ … not SHA2 or anything familiar. To see what kind of algorithm that is, you can visit this page . From that resource, ‘1.2.840.113549.1.1.11’ corresponds to ‘szOID_RSA_SHA256RSA’. This is a newer algorithm than Windows 2003 can handle, thus the patch is needed.
After applying the patch to the server and rebooting it, Outlook clients no longer received the error message. The certificate showed as valid via PowerShell and the Certificates MMC did not have any more red X’s on the certificate. The certificate also displayed the correct Algorithm as seen here:

So if you are having a similar issue, see what hotfixes are missing or are needed to support your particular servers needs.
Further Reading
Technet article on the issue