We had a similar issue with queries that didn't match an index... later pages would time out, etc... we limited our results for that class of queries... The next generation will use cassandra with some custom searching/caching... that will work a bit differently.
And we are actually considering ElasticSearch to deal with this querying performance issue.