Ti si potrebbe essere inchiodato il connetore pop3 di sbs. e quindi ti si verifica questa anomalia. Controlla che il serivio sia avviato. inoltre prova a rimuovere l' account pop3 dei 2 utenti e ricreali. vedi che succede e facci sapere.
non sembra un errore di certificato ma bensi un problema di allineamento del DB di exchange con l'utente.