I know generally queries on the GAE datastore are eventually consistent. However I don't see why queries on __key__ should not be strongly consistent as I presume this is what the datastore Get function uses.
Can anyone confirm querying by __key__ is strongly consistent?
A query will be consistent only on ancestor queries. Otherwise is not consistent even if the index contains key entries. This is because writes are applied in two phases, one to write your data and other to update indexes. Get by key neves uses an index so its always correct. I assume that you are generating semi-secuential keys otherwise a query with key wouldnt be useful. Beware however that appengine now recommends to spread your keys so they cover a large space and is thus better distributed in bigtable.