Restore the ~/Library/Mail folder and the ~/Library/Applications Support/AddressBook folder.
I've never recovered the whole Mail folder, so you might want to wait for other input.
I have restored the AddressBook folder and it works fine. It will also recover the previous recipients in Mail.