Buenas tardes, se me ocurre lo siguiente. Si de algunos usuarios que le envian no los ve, ¿podría ser que esos usuarios tuvieran guardado la dirección del usuario es su Libreta Personal de direcciones el usuario, con la llave vieja antes del cambio?

Revisa eso, tal vez esten enviando los correos cifrados pero con direcciones de la libreta personal.

Si esos usuarios que envian tuvieran activa la opción de Contactos recientes, revisar en la Libreta Personal tambien si estuvieran en dicha vista.

Saludos