Credo che la risposta stia nella diversa configurazione di rete dei due operatori.

Non vorrei che con l'introduzione delle notifiche push per le app di terze parti Apple abbia modificato anche il servizio push per le mail. Da quello che so, il software di iPhone gestisce il push in modo diverso in base alle configurazioni delle reti degli operatori partner. Non è da escludere che abbiano esteso questo "comportamento" anche all'e-mail, bisognerebbe vedere cosa succede con una sim Vodafone.

Per il passaggio da 3G a EDGE non saprei...