It does sound like the server is picking up new mail on rescan only.
There have been issues in the past with MS updates blocking UDP packets. Can't remember the specific updates.
Also, if your Exchange is remote and the link has high latency, there could be dropped UDP packets.
In your logs you will probably see "Queuing new mail through rescan" more than "Queuing new mail through notification"