Thanks Wibbly for sending me in the right direction!

This is really weird, but here is what caused it:

I moved from a BB7100 to my current 8800 and transferred all of my stuff (contacts, emails, etc.) So I had 3 months of email on my BB8800.

I did the backup thing as wibbly suggested, and was about to delete all of the mail from the BB. Just out of interest, I thought I would check the backup to see just how many messages were in my Inbox (ie. to see if it was over 900 or not).

Guess what the number was? 999 messages.

So apparently there is a hard limit of 999 msgs in your inbox. I think every time one got old enough to drop off, a new one was allowed in. That's why I was getting every other message (approximately). There could never be more than 999 msgs in the inbox.

Once I blew away the inbox messages, everything has been working perfectly since!

As a precaution, I have set the limit on the BB to 30 days for how long it keeps old messages.

Hope this helps anyone having this problem in the future.. definitely do a backup and see how many msgs in your inbox!