My initial thoughts are (I've got to go re read some of Ted's comments):
We keep track of the target layout and the current layout. The target layout would include things like nodes that are down - you would be able to tell a slice should exist even if all nodes serving that slice where down. The current layout would show how things actually are - what is up, what is down, etc.
I suppose you might track this all in one structure, but we want to think about what the separation might give us too.
For example, suppose we offer manual rebalancing control (supposing getting the heuristics right for auto is hard difficult or not always appropriate) - if a user where to move a shard to another node, he could make the change in the target layout. If the overseer goes down while making this change, the new overseer will be able to look and see that while a change was intended, it has not happened yet and the shard still needs to be moved. Meanwhile, clients will still be directed to the old serving node through the current layout.
On the other hand, clients will still have to read both current and target layouts to be aware of missing slices and properly handle partial results. It still does not give you "one place for all of this" that I remember Ted arguing for.