Tive um problema desses em um cliente com um servidor windows server 2008, sendo que depois de formatar o servidor e instalar o windows 2003, aparentemente estava resolvido. Fizemos isso depois de inúmeras tentativas frustradas de configuração, instalação do certificado em outras máquinas, etc.
Depois de alguns meses, surgiu o mesmo problema - detalhe: nas duas ocasiões o acesso ao certificado estava lento até mesmo diretamente no Internet Explorer.
Descobrimos então que isso acontecia por conta do armazenamento das credenciais no windows das máquinas que teriam que usar o certificado.
Nas máquinas clientes com Windows 7 é só ir no painel de controle - gerenciador de credenciais e remover todas as credenciais. Note que isso fará com que as senhas armazenadas para preenchimento automático em outros computadores/sites serão novamente solicitadas no próximo acesso.
Experimentem deixar o componente como estava originalmente e fazer essa exclusão das credenciais e então reportem aqui o resultado.