Thanks for sharing, this is a neat post!
(My understanding is-) the biggest philosophical / structural difference between makes / make-likes (incl. Bazel) and redo is that redo *does not* specify the dependency graph up front. So- I'm not sure if / how "strict dependency checking" would apply to redo without a philosophical shift?
Output isolation might be useful-
"RWC the output file and a temporary directory, RX everything else" as the policy? I'm not sure how that would play with the "rebuild directory as a side effect" pattern- maybe there are other decent ways of producing "an output directory" that would allow this isolation?