Já mám přesně ten stejný problém. Ještě můžu doplnit, že to nefunguje ani pod Netscape - tam se mi nepodařilo ani odeslat podepsaný email.
Dříve (skoro dva roky) jsem používal VeriSign a tam nikdy problémy nebyly. Vše fungovalo. Později jsem se rozhodl přejít na bezplatný Thawte - a ten se mi nikdy nepodařilo rozchodit. Přesně jak píše autor příspěvku.
Posledního půl roku používám klasický PGP.