Travis,
You have posted in the Mail & AB forum for Leopard, and not Snow Leopard, and the system info posting below any of your responses reports 10.5.6 -- you should correct the latter.
For some using Snow Leopard and using Time Machine, this has been leading edge issue, and one that hopefully will be dealt with by the next update to SL. What seems to happen with Mail 4.x and use of Time Machine, is that the file that in normal use prevents duplicate downloads gets restored to an old version, and thus Mail does not know it has downloaded the messages previously. Purging the MessageUidsAlreadyDownloaded3 file will cure briefly (after enduring one more download of all messages on the server, but the problem will return because of Time Machine. Are you using Time Machine?
As for housekeeping, if you quit Mail, and then shut down your laptop (or maybe even if only putting it to sleep by closing the lid), then Mail housekeeping tasks, which include keeping the index up-to-date do not get finished, and then can be problems. Now that I know you are using Snow Leopard, I am less suspicious of that.
Ernie