A mi me pasó lo mismo, solo que en el correo que viene en el móvil me funcionaba bien, me llegaban los correos de dos cuentas de hotmail y una de Gmail.
Me di cuenta que tenia poca memoria en el teléfono (19mb o menos) borré aplicaciones descargadas que se que no voy a usar o usar menos, desinstalar actualizaciones de aplicaciones que uso poco.
Y partir de ahí me empezaron a llegar los correos de Gmail, los diferenciaras porque en la barra de notificaciones cuando te llega un correo te sale el símbolo de gmail.
Borre la cuenta de correo en la aplicación "correo" del teléfono y solo me llegan a la aplicación de gmail
Creo que según he entendido la diferencia con Gmail es que no esta continuamente comprobando si hay correos nuevos, simplemente te envían un correo y te avisa (alomejor con algún retraso no lo he comprobado) .
Configuralo para que la etiqueta "recibidos" este en Sincronizar todo y si tienes también las cuentas de hotmail integradas en gmail ponlas también Sincronizar todo.
Así es como lo tengo yo y me funciona de lujo ;) La única pega que creo que esta en los correos en general es que el led de notificaciones dura parpadeando 5 minutos.
PD: Actualiza en el market la versión de gmail.
Un saludo y ya cuentas como te ha ido.