Quizás sea esto:
La cuenta de correo esta configurada como POP3 y no como IMAP.
POP3 se descarga los mensajes en el terminal, cuando lo borras solo se borra del sistema.
IMAP lo borra del servidor, trabajan juntos.
Lo primero que se me ha ocurrido, prueba y ya nos comentas el resultado.