Intermittent X509CertificateChain.Build Errors

We have a WebService on a server with an X.509 Cert and several web sites that will hit the web service over net.tcp. The Cert has been working for almost 2 years without issue. Suddenly, last Friday we started getting this error in our Event Logs of both of our Web Servers.

OID values and CN are scrubbed.

The X.509 certificate CN=www.ourdomain.com, O="Our Domain Services, L.P.", L=Houston, S=Texas, C=US, SERIALNUMBER=11111111, OID.1.1.1.11=Private Organization, OID.1.1.1.1.1.1.111.11.1.1.1=Texas, OID.1.1.1.1.1.1.111.11.1.1.1=US chain building failed. The certificate that was used has a trust chain that cannot be verified. Replace the certificate or change the certificateValidationMode. A certificate chain could not be built to a trusted root authority.

This error is quite sporadic, but was happening enough to cause our clients quite a headache trying to use our system. I was able to reproduce the issue from a Chrome browser, but if I tried a second time, it works. However, a customer may not have the patience to try over and over again until it works.

We've search far and wide and for 3 days now trying to find folks who might have experienced something similar. Any results that came even slightly close do not have responses from the community. Ugh.

We've tried setting the revocation mode to NoCheck on web configs (although our error doesn't say anything about that), but we still see the issue present itself.

It started last Friday July 6, 2018, got much worse the next day, continued through Sunday (but not as often). By Monday the errors appeared to stop around 2am, but sure enough we got several more though the day. Even on Tuesday, although only once so far, we saw it again.

Our Web Servers are hosted on RackSpace. They assured us that there are no network issues.

Anyone have any ideas on what might cause this error to occur. But before you answer, please note: This doesn't happen all the time, so the Cert is GOOD, as are the intermediate and root Cert. Otherwise, it would not ever work at all.

Could network issues cause something like this to occur?

Any feedback, guidance or report of a similar experiences would be greatly appreciated.