For the last few months or so, Apple Mail has been just grindingly slow for me. I had no idea what could be causing the slowdown. I tried rebuilding the mailboxes to no avail. Just recently, I happened across this article purporting to have a fix to the slow mail client problem. I can happily report that after implementing the fix, it worked a dream! Mail is now speedy again. The fix actually purges the deleted mail from the mail database on your system and shrinks the mail envelope to a more reasonable size. You will obviously get the most performance boost the first time you run this. Enjoy.

See: Hawk Wings for more tips and tricks for Apple Mail