He tenido éxito utilizando el proyecto de código abierto geomodel para almacenar y consultar datos lat/lon en el almacén de datos de App Engine. Utiliza un geohash para permitir la consulta de una sola propiedad, está disponible tanto para Python como para Java y, dado que es de código abierto, puede modificar el código para que se ajuste a su caso particular si es necesario.
También vale la pena señalar que se anunció en Google I/O hace un par de semanas que el almacén de datos algún día (con suerte) proporcionaría soporte nativo para consultas geoespaciales y de fecha, utilizando una curva de Hilbert internamente. Esto permitiría consultas rápidas para el cuadro delimitador o incluso en consultas poligonales arbitrarias. Puedes ver el the video de esa charla en línea para obtener más detalles, es una discusión bastante interesante.