I use Opera for this. It is set to periodically fetch my mails from Gmail and I do not use its builtin mailer to send/receive/read mails (I use the web interface for that), but if I need a substring search then I open the Opera mail search panel and it allows me to dig through my past mail with substring search.

Edit: maybe it is doing prefix search only (I dont' know I search prefixes usually), so it's no true substring search, but prefix search is very useful in itself.