First of all, eventual consistency should be pretty safe, and such a "data housekeeping" process may not be mandatory. It may be indeed a feature to have several states of the data in the database. In BigData process, it is pretty usual - Google for instance may have several states of the same data in its servers.
IMHO your question may have answers at two levels, following the DDD architecture.
1. At Infrastructure Layer
You may write some code specific to the NoSQL engine you are using.
It would be optimized e.g. for fast process using KVP, perhaps with the following patterns:
- Using memory as cache as much as possible, to avoid unnecessary requests on the NoSQL;
- Run the operation in a separated process, to reduce impact on the main process;
- Let this separated process use a map/reduce pattern, then injecting the modifications as batches;
- Use some kind of CQRS pattern, and several databases: one KVP database for your direct writes, then dedicated secondary read-only databases, containing some "polished" data (also filled with map/reduce), ready to be consumed by your Domain Services.
Your idea of identifying "dead" keys is interesting. It could be implemented within the infrastructure layer, as part of the storage process, e.g. by maintaining an in-memory list of just written entries, then deleting then garbage-collect them using a generational-like algorithm, marking keys with a generation number, ready to remove the unused one.
2. At Domain Level
In DDD we try to be as uncoupled from the database as possible. As a result, doing some data cleaning process at infrastructure layer sounds somewhat weird.
Such data cleaning may be part of the domain, in a dedicated Bounded Context. The infrastructure layer, when apply the map/reduce algorithm, may use some logic defined in the domain, using domain objects, to validate your data, and fix any synchronization problem.
Last but not least, if your data seems eventually incoherent, it may smell like a domain problem. Your aggregates may be wrongly defined. What you should persist are Aggregates Roots, which scope has been defined by a given execution context. Typically, Aggregates are persisted in your database, and guarantee the consistency of changes by isolating their members from external objects (i.e. you can link to an aggregate via its ID, but you can not directly access to its internal objects). The eventual consistency of the KVP should be enough to ensure consistent data. If you encounter consistency issues, you may consider fixing your domain, which may have some problems about the Aggregate Roots scope.