Sehr wahrscheinlich liegt Ihnen von dem Kontakt ein alter oder falscher Schlüssel vor. Um dies zu beheben löschen sie den Kontakt UND das gespeicherte Zertifikat aus Ihrem E-Mailclient und legen den Kontakt dann neu an. Somit wird der neue Schlüssel gespeichert und das Versenden von verschlüsselten E-Mails funktioniert.