A: 

(SORRY I have no points for a comment)

I have the EXACT same problem, also! My code looks almost identical to what you have there, and the problem just randomly occurs about 1 in 5 times I'm debugging.

Unfortunately, we've also been getting the error on the version we deployed to the server.

I'll keep working on this and let you know if I find anything.

Thanks, Chris

A: 

I had this issue today and I believe I've figured out what has been causing it. The static method requires synchronization.

If you hover over your localStore variable at the time of the exception and inspect the Certificates property you'll most likely see something to the effect of "InvalidOperationException - To access the certificates you must use Open() or OpenRead()... blah blah blah".

What is happening is some thread is closing the store before another thread is finished accessing it.

I solved the issue by first creating a static class member for locking the store:

private static object m_storeLock = new object();

When you access the store you'll have to do something like the following:

public static X509Certificate FindCertificate(string certName) {
    X509CertificateStore store = null;            
    X509Certificate cert = null;

    lock (m_storeLock) {
        try {                    
            store = X509CertificateStore.LocalMachineStore(X509CertificateStore.MyStore);
            store.OpenRead();

            X509CertificateCollection col =
            (X509CertificateCollection)store.FindCertificateBySubjectString(certName);

            if (col.Count > 0) {      
                cert = col[0];
            }
        }
        catch {
        }
        finally {
            if (store != null) {
                store.Close();
            }
        }
    }                           

    if (cert == null) {
        throw new ArgumentException("Certificate not found!");
    }

    return cert;
}

To be extra safe, you should probably lock the local variable "cert", but this is not production code guys... :D~