Vale, después de haber configurado mi teléfono e investigar un poco por ahí, he visto que en la configuración del mail existe una opción para borrar los correos en el servidor.
Abrimos Correo -> Botón Menú -> Más -> Opciones (Ajustes) -> Enviar y Recibir -> Borrar correos en el servidor
Perdonad si no es exactamente así, tengo las opciones en inglés por culpa de la ROM y por ello sólo os puedo ofrecer mi traducción, pero estoy seguro de que será algo muy parecido
Para la configuración de la aplicación de escritorio que usas, dependerá de cual sea, pero seguro que existe una opción exactamente igual a la que hay para la hero, o incluso más completa. En Outlook se puede configurar que los correos se borren tras unos días después de haberlos descargado.