Buenos días,
Para ver cual puede ser el problema tiene que revisar lo siguiente:
-Que todos los gestores de correo que utiliza tengan marcada la opción de "Mantener copia de mensajes en el servidor"
-Que su correo no tenga ningun reenvio a otra cuenta. Eso lo puede comprobar entrando en el webmail: https://correo.movistar.es apartado Configuración > Correo electrónico > Reenvío.
- Que no tenga alguna cuenta configurada en IMAP en algun telefono movil o pc. Con este tipo de configurción, si borra un correo del dispositivo, se le borrará también del webmail, ya que esta sincronizado.
Revise todo esto que le he comentado, y si vuelve a tener problemas, nos lo indica.
Un saludo