Rubify

macOSXHints explains how his database stored phantom messages from an Exchange server he used over Summer. By quitting Mail application, dragging the Envelope Index folder to the Desktop, restarting Mail and allowing it to reindex his emails, cut its size from 200MB to 2MB. After, the Mail.app will definetely increase. Rob Griffiths reduced his from 25.9MB to 4.5MB.
There is still another way to do it, using sqlite3 command.
How to do it?
1. Quit your Mail.app
2. Open Terminal.
3. Type the following:

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

When the sqlite prompt returns, type Control-D to exit. Restart Mail and enjoy the extra speed. I reduced from 37.5MB of "Envelope Index" folder to 4.4MB . Quite cool.

rubify:~/Library/Mail chardy$ du -hs Envelope\ Index 
4.4M    Envelope Index

Cheer.