I have an iPhone 3GS with OS4 and have been struggling to get push email notifications from our companies exchange account. Chanan, a co-worker of mine, has an iPhone 4 and was experiencing the same issue. All of our phones settings were configured to receive push notifications but unless you opened the mall app it wouldn’t get any new email.
He found this blog post that outlines a solution if you are trying to get your iPhone 4 to stop getting email notifications when you don’t want it to which incidentally happens to be the same solution for this issue.
The problem is caused by a bug in the iPhone software that will hopefully be resolved by Apple but here are the steps for the temporary fix that you can use to get push notifications again:
Open up your running apps menu but pressing the home button twice to get this menu:
Now press and hold your finger on the Mail icon until it starts to shake and shows a little red – in the top left corner of the app
New press the little red circle in the top left corner to close the mail app so that it is no longer running in the background and doesn’t show up in running apps menu
Now as long as your other email settings are configured for push notifications you should now be getting push email notifications for your Exchange account again. You will have to perform these steps after each time you open up your mail app as it is the mail app running in the background that somehow breaks push notifications from working properly. Hopefully this will be resolved in a future release but this is the problem I am experiencing and I am using OS 4.0.2 (8A400).
Obligatory Moniker 