We use client SSL certificates to secure web-based user communications with our web server (the edit site for a SharePoint site). Certificates are generated internally and sent to users to be installed.
Normally we don't have any issues but lately some users have been unable to access the sites while others can authenticate successfully during the same time period and even using the same certificate.
A network packet capture suggests IE isn't always sending the certificate. At this point, uninstalling and reinstalling the certificate corrects the problem--but isn't desirable.
Are you actually validating client identity with the SSL certificate rather than just using a server-side certificate and SSL to encrypt the communication? If so, that's not a particularly common scenario (although you may have very valid reasons for doing so). If you don't have a business need to authenticate clients with certificates, you could still encrypt communications while turning off client side certificate-based authentication which would solve your problem :)
According to the IIS Authentication documentation on MSDN:
Is it at all possible that you have multiple CA's generating the client certificates, and for some reason one of them is not on the Server's Certificate Trust List (CTL)?
Do you have more than one applicable certificate in the client's personal store? If there is more than one certificate, IE might not be able to choose the right certificate, so it won't send anything. Does the server require client auth when looking at the network sniff?
When the issue is present, can you list the client certificate using certutil.exe? You can use certutil -v -user -store "my" and check for permissions/encryption test passing/other things that might look off. If there is something, you can try to find the root cause of it.