Can you post an isolated test case? When I get home later this week I can try to duplicate and confirm dev environment behavior with 1.5.1.
It sounds like you have discovered the new eventual consistency
behavior of the High-Replication Datastore. This isn't a 1.5.1 thing,
it should affect any HRD apps. Basically indexes are written
asynchronously so queries might show stale data - if you want to force
consistency you can do an ancestor() query to fetch it, or just do a
fetch by key.
There's a fair amount of talk about this here:
http://code.google.com/appengine/docs/java/datastore/hr/overview.html
Jeff
FWIW, I've found latency to be vastly better on the HRD. Since it's
soon to be priced identically to M/S, you might seriously want to
consider switching... although you'd have to figure out a solution for
the query consistency issue.
Jeff
Jeff