BoingBoing has an incredible tip on speeding up opening and searching through mail folders.
After amassing an OS X Mail.app folder of several gigs of email, search and opening folders was getting sloooow on my 1.67 Ghz Powerbook.
I didn’t to any before/after measurement, but the after performing the simple commands, searches through umpteen-thousand emails took blinks of an eye instead of 20 or so seconds. This tip is highly recommended. Make sure to back up your ~/Library/Mail folder first!