Shame about Greplin - I didn't use it particularly regularly, but I loved that it was there if I ever wanted to delve back to something I half-remembered, like a long-lost tweet.
On the other hand, my copy of "ReMail", the first iPhone Gmail indexer (which got bought by Google, discontinued, and open sourced[1]), is still going strong on iOS 6 with a quarter million emails in its offline index.
http://help.cueup.com/customer/portal/articles/25915-getting...
I interacted with Greplin support, they were aware searches weren't finding things that had been auto filed by Gmail rules into labels. I have been annoyed this "for pay" service didn't handle this.
(Note that I do not expose the "All Mail" virtual folder through IMAP because that ends up doubling mail.)