Restoring .emlx files to Mail.app
Your emails are stored as .emlx files and once located can be viewed via Mail.app by double-clicking on them.
That's great but you cannot import these files directly into Mail.app. You cannot drag and drop them into Mail.app. You cannot "Rebuild" them. Forwarding them to yourself could take a great deal of time and you would loose any ability to run "Rules" on them via date sent/received, sender, etc. So, what do you do?
1) Locate your .emlx files:
You can generally find them in your user directory using "Finder":
<UserName>/Library/Mail/Mailboxes/<YourMailbox>.mbox/Messages
NOTE: Words inside are unique to you, replace them with your username, etc.
I say "generally" because you may have mail folders and/or imap folders which will create more layers of directories under your <UserName>/Library/Mail directory. However, if you go to your <UserName>/Library/Mail directory you should recognize your Mailbox, Mail Folder, or imapFolder names and easily find your .mbox/Messages folder inside, which will contain your .emlx files.
2) Download a .emlx converter:
Once you have located your .emlx files you need to convert them to a format that Mail.app can import. This would be .mbox. Why Apple stores your emails as .emlx but can't import a .emlx is beyond me. Send Steve an email!
Download this free utility to do the conversion:
http://www.cosmicsoft.net/emlxconvert.html
I have only used the Max OS X version not the Windows version, I did not write this, do not own it, have nothing to do with it's development, etc. So, follow the procedure described below at your own risk. However, I did use it for several thousand emails and it worked great. It is free but as a supporter of freeware I would suggest that once you recover all of your emails you send the person who wrote this a token of your appreciation via PayPal. After all, his or her effort just saved your email rear-end. You will see the "Donate via PayPal" button when you run the application.
3) Convert your .emlx files:
Run the .emlx converter.
Drag the .emlx files you want to restore from the directory you located in Step 1 onto the Converter dialog box. I would suggest you do this in an organized fashion. For example, don't do all of your emails at once. Think about it a little, organize yourself and have a little patience. I know that's hard since a lack of this planning is most likely how we lost our emails in the first place.
So, I would do one Mail Folder at a time. This will make it easier to reorganize your emails once they are back in Mail.app. If you have a "lot" of emails in each folder I would do a "little" at a time. What is a "little" and a "lot"? Well, that's subjective but I only converted about a 100 emails at a time. If you feel frisky go for more.
Click "Save mbox"
Choose a name and location to save the mbox to.
4) Import into Mail.app
In Mail.app select File->Import Mailboxes...
Select the "mbox" or "Other" radio button from the Import Screen, Click "Continue"
Select the Directory/Folder and filename of the .mbox you created in Step 3, Click "Choose"
Import will occur.
Select "Done"
5) Thank God for script writers and send the guy some money.
6) Reorganize your emails
You will now see an "Import" folder in Mail.app.
Your emails are in there and can now be dragged and dropped back into their respective email folders.
If you do each Mail folder separately, like I suggested in Step 3, you will see more then one "Import" folder. They will be numbered "Import-2", "Import-3", etc.
7) Try not to delete all of your emails again....