Las cuentas hotmail no usan imap, sino pop3, esto quiere decir que una vez conectado a una cuenta con un programa externo en un ordenador (como Mail o thunderbird por ejemplo) el servidor lo único que hace es permitir la entrada del usuario registrado y permitir la descarga de estos correos al ordenador, para que el usuario pueda "trabajar" (leer, responder, reenviar, guardar, lo típico, etc.. ) sobre ellos.
Lo que significa que aun que borres un correo en tu ordenador, estos no se borran en el servidor, salvo que Mail lo tengas configurado para que así sea (que generalmente la gente no lo hace), y Mail no es tan "avanzado" como para que lo haga solo.
Si te han volado correos de tu servidor de hotmail, lo mas seguro es que sea Microsoft que por un error te los haya borrado, o bien que los hayas borrado tu desde otro correo o servicio web, o bien que te hayan hackeado la cuenta y hayan entrado y te los hayan borrado (cosa poco probable si no vas regalando tu nombre de usuario y tu contraseña a diestro y siniestro) o que por tiempo, el servidor los ha eliminado para ahorrar espacio.
Luego, el tema del iPhone es mas bien un problema de sincronización con el ordenador, lo mejor que podrías hacer es restaurarlo y volverlo a sincronizar, es posible que la primera vez no se te copiaran todas las configuraciones de todas tus cuentas...
