I have this stupid symptom with my mac mail since upgrading from 10.6 to 10.7.
I have multiple exchange accounts; a couple times a day the inbox for 1 or 2 of them will be blank, quitting mail and re-opening will re-download all the mail.
Search also only works by person, not 'message contains'
So - I made a new user, everything works perfectly. Symptom gone.
I formatted and restored from time machine, still have the problem.
This is a dev box with tons of customization - I want to properly PURGE the mail and accounts settings at the file system level, since I know a 'new user profile' is a proper fix for the problem.
Emptying the mail folders doesn't fix it, it re-downloads everything and the problem is still there.
Removing the accounts and re-adding doesn't fix it either.