Yo utilizo la aplicación de correo nativa para mi cuenta de @msn y me funciona bien.
Unas cuantas cosas:
1) No se te sincroniza cuando estás con wifi o con datos?
2) Tienes bien configurado los APN?
3) Has configurado bien el servidor exchange?
Ya nos cuentas, ok?