at google io 2010 they discussed "next gen" queries in depth, which should be able to do geospatial queries easily (or any query for which your search space can be filled by a space filling curve):

http://www.youtube.com/watch?v=ofhEyDBpngM

we still haven't seen any of these improvements. in fact, they took it off the roadmap without any explanation.