There has been a lot of work in the last 10 years on search over encrypted data. Some of the more practical schemes do operate similar to how you describe; searching over encrypted indices. For example, check out Chang & Mitzenmacher's "Privacy Preserving Keyword Searches on Remote Encrypted Data": http://eprint.iacr.org/2004/051.pdf

There has also been a lot of theoretical work in topics like predicate- and functional-encryption which could eventually be used for richer queries.