Envelope Index (see “What’s in your Mail folder?”) is an SQLite database that stores key information about your emails. Over time it can get terminally corrupted (see “The dreaded ‘your home directory is full’ message”).
It can also suffer a large number of smaller hiccups and corruptions which slow Mail down, although they don’t knock it out.
A poster on macOSXHints explains 
how his database stored phantom messages from an Exchange server he used over Summer.
Quitting Mail, dragging the Envelope Index to the Desktop, restarting Mail and allowing it to reindex his emails, cut its size from 200MB to 2MB. The speed increase was significant. Rob Griffiths reduced his from 25.9MB to 4.5MB.
My result was less dramatic (21.6MB -> 17.6MB) but Mail.app still feels a little more zippy.
Worth a shot for you too, perhaps? If so, first make sure you have a backup of your ~/Library/Mail folder in case something goes wrong. Dragging it out of Finder onto your Desktop will do the trick.
[...] if youre Apple Mail does not allow anymore to search for “entire message” then try out this following fix Trick [...]
Hello,
I new in the MacBook world, and I configured my student e-mail account, in the first time I did this I received the e-mail correctly, but in the next day MAil couldn’t connect with the server, so, i re.configured the account. And it worked great until today.
I tried to see an e-mail from august 22, and it was blank, and all the older e-mails, i click on rebuild because i thought that that option would bring them back… so i know it doesn’t… what can i do?? all my e-mails will go blank?! can I recover the e-mails i lost?
thank you!!
apple has a knowledge base article on this — reindexing all messages: http://support.apple.com/kb/TS1907 [mac os x 10.4, mail: messages seem to be missing, or "message has not been downloaded" alert appears when opening]
it seems that if you use mobile me or imap then one important additional step is required, before open mail again, namely “Move any folders in ~/Library/Mail/ that begin with “Mac-”, “Exchange-”, or “IMAP-” to a different location, such as your desktop”
so here a copy of apple’s advice:
Reindex all messages:
a) Quit Mail.
b) In the Finder, choose Go To Folder from the Go menu, and go to ~/Library/Mail/ .
Or, choose Home from the Go menu, then open the Library folder, then open the Mail folder.
c) Move the Envelope Index file to a different location, such as your desktop.
d) Move any folders in ~/Library/Mail/ that begin with “Mac-”, “Exchange-”, or “IMAP-” to a different location, such as your desktop.
e) Open Mail. Mail will reindex all messages. This process may take several minutes depending on how many messages you have in your mailboxes
My mailbox is enormous (24,000 messages). When I tried sending a huge message by accident (20MB) I got the dreaded “your home directory is full message.” Since then I have tried dragging the envelope file to the desktop, dragging the envelope and the mail cache envelopes off, and deleting the offending 20MB file out of my outbox folder. So far nothing’s worked, and I just get an endless beachball after Mail rebuilds my index and I start it up. Any suggestions?
[...] Tip from Hawk Wings. [...]