Yo tengo Movistar, y uso la desire...
Y me pasa lo mismo, a veces llegan bien (unos segundos) y otras veces (demasiadas veces) me tarde mucho... más de media incluso.
Vengo de la Palm Pre... misma conexión (Movistar) mismo servidor de correo (Gmail... concretamente Google Apps), y con la Pre no fallaba NUNCA... pero con Android... estoy bastante decepcionado en ese aspecto, la verdad.
He probado todo lo que se me ha ocurrido, como jugar con la configuración APN, pero nada.
Lo que no he probado (a ver si tengo tiempo) es configurar una cuenta de gmail como cuenta de "Exchange Active Sync", tal y como dicen aquí:
http://www.google.com/support/mobile...?answer=138740
¿¿Alguien ha probado a hacerlo a ver si así funciona bien el correo push???