We have some APEX code in a Salesforce application that makes a callout to an external service we've developed.  We already have clients consuming the external service without issue from outside of Salesforce (via .NET, Java, PHP, etc.). 

Our testing in Salesforce, however, has shown that the callouts fail when they are made to our external service due to a certificate issue.  

System.CalloutException: IO Exception: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

Based on what we are seeing, the issue appears to be related to the certificate chain for our certificate.  Our certificate was issued by Network Solutions and we've found that they (essentially) provide two alternate certificate paths:

/C=US /O=Network Solutions L.L.C. /CN=Network Solutions Certificate Authority
    >> /C=US /O=Network Solutions L.L.C. /CN=Network Solutions EV Server CA
        >> /C=US /O=[Our Company] /OU=IT /OU=Secure Link EV SSL /CN=[Our Domain]

and

/C=SE /O=AddTrust AB /OU=AddTrust External TTP Network /CN=AddTrust External CA Root
    >> /C=US /O=Network Solutions L.L.C. /CN=Network Solutions Certificate Authority
        >> /C=US /O=Network Solutions L.L.C. /CN=Network Solutions EV Server CA
            >> /C=US /O=[Our Company] /OU=IT /OU=Secure Link EV SSL /CN=[Our Domain]

What we've found is that the "Network Solutions Certificate Authority" certificate root in the first chain I posted has the same keys as the second certificate in the second chain I posted (which shares a CN, etc.).  Given their matching signatures, they are both treated as valid signers of the "Network Solutions EV Server CA" certificate.

From what we've been able to determine, the first (shorter) chain represents the newer chain being used by Network Solutions and the alternate chain is there to maintain some sort of compatibility.  

The issue seems to be that Salesforce recognizes the AddTrust root certificate (present in the secondary longer chain), but not the Network Solutions root certificate for some reason.  Both roots are installed on the servers hosting our external service, but the chain the servers respond with is the first chain not the one containing the "AddTrust" root.  The result is that Salesforce doesn't recognize the validity of our certificate even though it is in fact a valid certificate.  

Based on these findings, it seems like the issue is that Salesforce does not include trust for the Network Solutions Certificate Authority root certificate?  Is this an oversight or is there an explicit reason for this behavior?

We can't make changes to the certificate behavior on our external servers without impacting our non-Salesforce client usage of our service, so we need to determine how to get this working with Salesforce.  Any assistance that can be provided would be greatly appreciated as this is client-affecting.