"A typical scalable database engine like App Engine's Datastore will only look at each entity in isolation. Since the entities are technically fine in isolation, there's no guarantee of consistency from the engine level."

This is not true. A feature in app engine called entity groups were added to work around exactly this type of problem. The Dog entities should have their entity group (parent) set to The DogWalker. This will ensure full read/write consistency among that group of entities.

Combine this with transactions, and cross-entity-group-transactions, and you can ensure that you don't have dangling or incorrect pointers like what you describe.