How to search Mail in Time Machine?
Emails are stored in sub-directories located in ~/Library/Mail/V2 in .emlx format. This allows you to do a global plaintext search within a specific time machine backup folder.

I wrote a shell script to search for text within all .emlx files in a specific time machine backup.

Alternatively you can do a drive search in terminal (what my script automates). Replace Search Query with what you want to search for:

find "/Volumes/Time Machine" -name "*.emlx" -exec grep -l "Search Query" {} \;


Or also replace /Volumes/Time Machine with a more specific directory to speed things up e.g /Volumes/Time Machine/Backups.backupdb/stan/2014-09-16-084603/