My 4+ gigs of email were making Mail.app slow, but I found a great tip over at Hawk Wings (a great site for mail related tips) for cleaning up the databases the Mail.app uses to speed things up.
Basically it involves:
From the Terminal type:
sqlite3 ~/Library/Mail/Envelope\ Index
When sqlite3 comes up enter:
It will go away and churn for a few seconds to a few minutes and when it is done restart mail and it should be faster.
A script that automates this and more info is available at http://www.hawkwings.net/2007/03/01/a-faster-way-to-speed-up-mailapp/