Apple Mail keeps a lot of junk in a SQLite database named Envelope Index. Since it’s a database, it tends to grow with time, and deleted records are not handled very efficiently. You might want to clean it a bit from time to time, and Mail might even seem a little faster after that.
1. Quit Mail
2. Launch a terminal, and type this command :
sqlite3 ~/Library/Mail/Envelope\ Index vacuum