So I have a stock Incredible, with 2.2 on there. I am using the native "Mail" app. I am connected to the exchange server with no issues. I have the thing set to "As Items Arrive" for BOTH peak and off-peak so that I can get messages pushed all the time.
It seems to work intermittently, sometimes it does get the emails pushed and bings at me. Other times, it seems to never initiate a sync and just sits there. If I pick it up, turn it on, I can force it to sync and then it gets the new mail.
(I know about touchdown, and I may consider it but for now I want to see if I can fix this)