I recently moved all of my Mail accounts and messages over to our new iMac, using the Migration Assistant that comes as part of OS X. Everything seemed to work fine, in fact, although it took a long time to transfer the files, Mail was up and running with minimal fuss.
However, when I came to search for an old email, I could not find it. Mail would only give search results on emails that had arrived or been sent after the transfer. A quick search found this Apple document on the issue. I am happy to say that re-indexing the messages solved the problem. In my case though, I only moved the Envelope Index file and not any additional folders.
