The guru of all things Mail.app, Tim Gaden at Hawk Wings, has posted a tip that seems to offer a considerable speed boost to Mail. Basically performing the tip strips the "bloat out of [Mail's] Envelope index, an SQLite database Mail uses to store senders, recipients, subjects and so on." It requires a little bit of terminal jockeying, but this is limited to running one command using sqlite3. Tim himself reports considerable speed gains, as do many in the comments. As always, backing up before attempting such things seems like a good idea, but quite a few people have performed the trick without adverse results. Check it out for yourself over at Hawk Wings.