Click on the Finder icon, then press shift-command-g. This will open up a dialog where you can type a direct path.
~/Library/Mail/ and press return. You should be able to see a folder called something like 'V2', and possibly other folders with similarly cryptic names. Open them and look for your mail messages. If your mail messages are hidden anywhere on your computer, they will be somewhere in these folders. If they are not here, then I hope you still have access to the messages online, or have made a Time Machine backup of your computer, because they are gone from your mac.
If you have made a Time Machine backup, then keep the Finder window open and and go to the Time Machine menu and click 'Enter Time Machine'. You will be able to travel back in time through the folder looking for your messages.
If you still have the messages available online, then you should be able to setup your accounts again and re-download the messages. (If you are using IMAP, then the messages should all download automatically when the account is setup, but if you are using POP you may have to go online and change your POP download settings to allow all mail to be downloaded.