Point storage with radius queries are nice and all, but I'd love to find a cloud storage provider that stored polygons and took polygons as queries, and had pay only for what you use.
Someone just tweeted at us earlier about GeoJSON (http://geojson.org/) which looks pretty awesome for storing polygon data. It sparked a conversation internally about a feature like that, especially since SimpleGeo (which offered that, I believe) is gone.
That point aside, geofencing queries are coming soon. That means that instead of just giving a center point and radius in your query, you can query with a polygon defined by arbitrary points and we will return your objects that exist inside that shape. Perhaps that could hold you over for the time being?
Storing polygons is probably key - if there's a query-by-radius or bounding box I can make an enclosing circle for my query and then do my own intersection tests with my query polygon.