Yo diría que eso depende del tipo de conexión que hagas para bajarte los correos al teléfono, si estás usando un tipo de conexión pop deberías poder configurar hotmail para que te borre los correos una vez hayan sido descargados en tu teléfono o en tu pc. Por otro lado si la conexión fuera imap, no deberías tener ningún problema dado que lo que se hace con este tipo de conexión es trabajar directamente en el servidor, de forma que correo que modifiques-borres debería reflejarse en el acto desde todos los puntos de conexión que hagas a dicho correo.
Buscaré a ver si es posible cambiar la configuración de hotmail para ayudarte a resolver tu problema.