Boy does this sound familiar.
I would presume that you have a firewall and that you Exchange server is either in a DMZ or on the outside. If this is the case, (which it was mine), then your problem is that new mail push notifications use indiscriminate UDP ports for transmission, and do not pass through will standard port allowances. The way I solved it was to put a lightweight box in the DMZ hosting OWA and the IMS. My mailbox server could then reside on the inside unobstructed by the firewall. It seems as thought the Servers can push through to each other without a problem with the standard port allowances.
The result- instant mail notifications.
I have heard of other ways of doing this but could not make them work.
Al
atc-computing@home.com