Looking at certificate in the Windows Certificate Manager (certmgr.msc). Windows says it "does not have enough information to verify this certificate". When looking at the certificate path, the only certificate that is shown is the certificate itself (with a yellow exclamation mark), and the Certificate status indicates: "The issuer of this certificate could not be found".
I looked carefully at the details of the faulty certificate to find why is it different from other certificates. The issuer's name was clearly correct so this wasn't the problem. The field that drew my attention was "Authority Information Access" The reason was is that it contained extra data with a "URL=http:...name_of_domain.cer". This link is to the intranet the organization uses. I've downloaded the certificate on the intranet and installed it on the client. The certificate became valid, and now it shows two certificates in the "Certification Path"
Conclusions.. It turns out Windows XP is dumb for two reasons:
- Installing a certificate that has a chain to the Trusted Root Certificates is not enough for Windows XP. it tries to validate the Root Certificates up to their top of the chain (This doesn't make a lot of sense, since it should be a Root Certificate, and since Windows 7 doesn't follow this behave and accepts the certificate as valid).
- Since both the certificates held the same Common Name, Windows XP fails to show that the original certificate does have a chain. and made it alot more difficult to track down the issue.
Hope this helps anyone who will encounter this in the future. (or not since Windows XP supported ended, as we all know:) )