Looks like the place to chime in. I set up a Droid Incredible for one of the attorneys at my office and he seems to be having the same problem. We have his Gmail working fine, but he claims to only received 1 of the 19 emails from over the weekend.
We don't use MS Exchange, so I set up his work email with POP3. While doing so, I noticed that as I would send test messages they would arrive quickly, but the preceding emails would disappear. I was confused since they didn't show up in the trash bin.
Anyway, on his work station I just told Outlook to keep a copy of messages on the server for 5 days. Since this option was not previously turned on, I'm sure that messages were just being deleted in due course as the unit would sync with the server. Thus, his work station had the emails, but the Droid would only maintain them until the next sync, which means he only rarely happened to notice that any mail had come through at all.
That's my 2¢.