email client had me banging my head against a wall again when I finally dug up this tip on rebuilding Mail.app's 'Envelope
Index' SQLite database at Hawk Wings (If you're wondering what that file is all about, check out Hawk Wing's
"What's in your Mail folder?"
post). Forcing Mail.app to rebuild this file is as simple as quitting the app, browsing to your ~/Library/Mail/ folder
and dragging out the file called 'Envelope Index' to your desktop (I'd recommend making a backup of your Mail support
folder before attempting this. Don't say we didn't warn you). Start Mail.app back up and it will give you a message
about re-importing or re-indexing all of your messages (sorry, I forgot to screencap the message), and depending on how
many you have it could take a couple minutes. I have over 13,000 emails and it didn't take my G4 PowerBook long at all.
My Envelope Index was over 300 MB before I started this, and after it was all said and done that file weighed in at less than 4 MB. Putting Mail.app on this kind of a weight loss program can seriously speed it up and generally improve its performance; no more clicking on a new message 10 minutes after Mail.app notified me about it only to be greeted by "this message has not been downloaded yet..." silliness.
It is also worth mentioning that this tip is probably more of a troubleshooting technique than something you should work into your regular maintenance tasks. A commenter on this tip at Hawk Wings pointed out that this rebuilding operation nullifies a couple of mailbox settings. If you have set any specific IMAP mailboxes to be used for trash or junk, Mail.app will forget those settings after this rebuild. Still, I think the performance gain and all-around less-schizophrenic behavior of Mail.app was worth having to reset a couple of preferences.
[UPDATE: Some commenters have pointed out that Mail also has a Rebuild option under the Mailbox menu (at least in Tiger). I tinkered with this on one of my 4 IMAP accounts and it seems to do the same trick with far less fuss. Thanks for the tip!]