Haystack supports fast 2d+criteria searches, but right now is limited in terms of the way the criteria can be specified, and to a single additional field. Also is not integrated with general query optimizer/planner. May be worth enhancing along with more general pluggable index type enhancements.
User case is basically all users who want to do fast "find all restaurants that serve thai food 10 blocks from NYU" searches with large data sets.