If you "run out of entropy", then you are using /dev/random, and you should not. You should use /dev/urandom. The whole concept of "running out of entropy" is based on a flawed metaphor in which randomness is viewed as a kind of gasoline. That's just wrong. Recent versions of the man page of /dev/random (on Linux) are less terrible than what they used to be, and now recommend the right thing, which is to use /dev/urandom.
(When I say "you" it might be "the software you use". Regardless, someone is doing a stupid thing, and that stupid thing probably involves /dev/random.)
In any case, certificate validation entails verifying digital signatures, and there is no need of any kind of randomness for that (at least with "normal" signature algorithms like RSA, DSA or ECDSA).
Edit: actually, while the basic certificate validation uses no randomness at all, the checks for revocation status entail contacting external servers to download CRL or OCSP responses, so that's network traffic which may stall and thus display symptoms similar to a blocked read on /dev/random. And the protocol to obtain an OCSP response may include a random nonce included by the requester (here, the server), so it is conceivable that a read on /dev/random still lurks in that code. That's a bit far fetched.
