Tive exatamente este mesmo problema em 2 clientes diferentes com certificado CAIXA (A3).
Tentei de tudo também, Reinstalação do software charismatics, troca de pc, de S.O Windows XP ou 7 (32 e 64Bits) e sempre o mesmo problema Erro 403.16, já em ambiente de homologação tudo perfeito!
O cliente chegou a adquirir outro certificado da Caixa e mesmo assim o problema continuou, então mudou de certificadora.
A internet de um deles é ADSL OI, ainda não testei aqui na empresa que é GVT, mas se funcionar creio que a melhor alternativa seria a utilização de proxy apenas para comunicação com o webservice.
