For my future reference. Taken from hawkwings.net

Get a considerable speed increase in Mail.app (and if you’re lucky, a smaller mailbox size as well) by performing certain Terminal commands.

1. Quit Mail.app
2. fire up Terminal
3. Do/type the following:

$ sqlite3 ~/Library/Mail/Envelope\ Index vacuum .exit

If for some reason the single line method won’t work, then do the following instead

$ cd ~/Library/Mail
$ sqlite3 Envelope\ Index
sqlite> vacuum subjects;

1. Press Control-D to exit Terminal.

In case you didn’t know, the $ is your shell. Again Mail.app should NOT be running when you do this!¹ It’s also good practice to back up your ~/Library/Mail folder just in case. You have been warned