I have several different options for you, since troubleshooting a potential PKI can be a complex issue.
CRLs are slow, cumbersome beasts...
First of all, I'm going to tell you that CRL timeouts have led the largest PKI in the world not to use CRLs for the vast majority of PKI validation needs. Downloading a 50MB file when a user just needs a simple yea or nay before sending off an encrypted email is a non-starter!
How to do Validation
1 - You can test a replacement Microsoft's native validation client with a 3rd party validation client such as Tumbleweed or others, then monitoring the 3rd party validation client (as a control). Tumbleweed/Axways sells and provides trials of a popular 3rd party validation client, OCSP repeaters and responders. You can also use OpenSSL, ejbca, or OpenCA as validation responders. Additionally, there is an OSS framework PKIF, that includes specific CAPI logging functions, and OCSP clients located at http://pkif.sourceforge.net/
2 - You can control the validation data sources (CRL, OCSP, SCVP).
3 - Another source of problems may be slow DNS resolution, a lack of DNS caching, or misconfigured PKI, missing trusts, or the time required to refresh CRLs (causing a temporary hang if a larger PKI).
Can you share more detail about the configuration of the applications, the PKI itself, the fields to the x509 certificates, bandwidth, etc. In particular I am interested in the fields relevant to validation, such as the Authority Information Access (AIA) field for example, and any hardcoded references to CRL or OCSP.
Keep in mind that there is well-known ambiguity in the response types too. The RFCs specifically for OCSP have issues in that a good response and an unknown response are equally valid for a certificate of which the validation has no knowledge.
A discussion of Alternatives:
There are two main methods of doing certificate validation, white-listing and black-listing.
Black-listing protocols include CRLs, OCSP and SCVP, and then variations of OCSP.
White-listing on Windows can be performed using OCSP interfacing with a CA DB, CTLs*, and SCVP.
In most cases, white-listing methods are considered superior, more secure, faster, more real time, and better alternatives to black-listing methods.