Allora,
se vai su una mai del contatto, che ti dà problemi, nelle intestazioni non c'è una chiave (o simile può dipendere dal tema in uso), su cui puoi leggere i dettagli sul certificato usato?
Dovresti vedere una voce:
certificato rilasciato da:
che nome appare?
Riporta anche tutto l'errore restituito da TB.
Se in passato non ti ha dato problemi forse dipende dal fatto che le mail non erano state firmate digitalmente.
PS: quello è l'indirizzo mail valido di una persona o società? Nel qualcaso lo camuffo per motivi di privacy.
Edit2:
In Strumenti -> Avanzate -> Certificati -> Mostra Certificati -> Persone
riesci a trovare il certificato di quel contatto? Se si, selezionalo, vai su modifica e vedi se ti consente di segnarlo come fidato.