The first, and most obvious thing, is to slim down your mailboxes a bit. Create a new folder in Mail and move all your old emails into that folder (or use the Archive function if you have a Gmail account. This way Mail only has to load the most recent emails when it launches and instead of having to synchronise a list of over 20 000 emails with the server it only has to deal with 500 or so, saving your precious bandwidth if you are on a mobile connection.
It is also a good idea to rebuild Mail’s Envelope Index now and then. Mail application uses the (SQLite) Envelope Index database to index and search messages. By rebuilding this database, issues concerning messages that appear incomplete or are missing can be corrected. This feature may also improve Mail's performance. Just launch Cocktail, go to System > Databases and click on the Rebuild button.
You can also use Cocktail to clear Mail downloads. When you receive attachments to e-mail messages, the files are stored with your messages at first. But if you double-click an attachment to view it, Mail stores a copy in a folder on your hard drive. You may have dozens of files there occupying a huge amount of space. You can generally delete these without worry. If you still have the original messages, the attachments are part of those messages. All you have to do is to make sure that the “Mail downloads” option in Cocktail > Preferences > Caches > Internet is enabled next time you use Cocktail to clear Internet caches.
Another housekeeping tip is to clean your previous recipients list. Mail stores a list of everyone you’ve ever sent a message to so that it can suggest their email addresses when you are writing a new email. The problem is that many of these recipients are people you only emailed once, or addresses which have changed so the list can become full of out of date and irrelevant addresses. Select Previous Recipients from the Window menu in Mail to clean up the list.
Finally, if you are using Mail to read RSS feeds it might be a good idea to go through your subscriptions and deleting the ones you no longer read as Mail essentially treats an RSS subscription as a mailbox. This means that as the number of posts increases Mail will slow down, so keep an eye on your feeds!