Hola, yo tambien tengo el correo de office365 y antes tenia telefonica.net y me funciona perfectamente.
Lo que tienes que hacer es llamar a movistar, pedir por el servicio tecnico y ellos te ayudaran a configurar el gestor de correo (yo uso Outlook) con los protocolos y los puertos.
si utilizar Outlook, amndame un privado y te dare los datos de configuracion si no quieres llamar a movistar (la llmaada es gratis) 900101010 ó 1002.
Si los correos se borran es debido a la confiuracion del gestor de correo, que es el que los borra o los puede guardar en el servidor durante un tiempo