Yo estoy usando ahora Maildroid y ningún problema. Bueno, hasta que intenté configurar el correo de hotmail por exchange, no sé porqué pero no se deja... en cambio con la aplicación de "serie" lo hace sin problema.
K9 o Kaiten también funcionan con push. Aunque con Kaiten también intenté la configuración de exchange para Hotmail y tampoco funciona. K9 lo usé mucho tiempo pero elegí Maildroid porque me permite crear reglas.
Tienes la aplicación de Hotmail en el Market:
https://market.android.com/details?i...RtYWlsLlo3Il0.
El correo te llega por push también pero mirando con el programa BetterBatteryStats es uno de los que más "wakelocks" tiene, o sea, que no deja dormir al teléfono.