Trust me, it's nothing that you are doing wrong, I'm an exchange administrator and I can't get it to work correctly - I think that the latest software update they did which fixed the incorrect contacts might be the problem that is causing the 'push' to fail.
There is a number of forums posts about this subject on the motorola site and other android related forums and no one seems to have a fix for it yet.
The only true way to get your email 'almost' instant is to use a 3rd party app called 'touchdown' which you can find in the market place (make sure you get 2.x version).. you get a 30 day trail - hopefully they will have fix the issue by then...
I'm like you, i need to be connected at all times for my work..
I hope this helps...
Are you ruuning Exchange 2007 or Higher?
I think that this problem is only for Exchange 2003 users.. I just read on the Motorola site that they have already issued a patch to Verzion for testing and to be sent out OTA which will hopefully fix the issue but now that i've used Touchdown more, i like it better then the moto app.