If you're using exchange on the Droid, spend the extra money and get the Touchdown for Exchange app. It's a much better experience.
Also... when you notice this, do you check for data coverage? I noticed that a few times, I have to kick my device out of sleep and then play with the browser to get 3G back.
At that point, the email will come in.
I turned off Wi-Fi, BlueTooth and the MissedCall app. Powered off my phone and then back on. So far, both Exchange and Gmail have been instant...
Thanks for everyone's help so far. I'll see how the rest of the day goes.