I admit that I've almost totally forgotten about the "random" part.... I myself have never seen timing issues (other than broken OCSP responders or certificate authorities with huge CRLs; with digicert this should not be a problem), but this is just personal experience.

There are two other questions to narrow down the problem:

• Does it work with browsers or do they have the same random issues? If browsers work just fine, this would point to a problem with Perl's libraries but still leave the question why your client works with other HTTPS sites.
• Is this "one server" or something load-balanced? Check whether the server's name resolves to more than one IP address, and if so, point your client or OpenSSL's s_client to the individual IP-adresses and check whether it makes a difference.