Consider this makefile rule:
foo.a: $(patsubst %.c,%.o,$(wildcard *.c))
Now, the foo.a target will be considered as stale if any of timestamps of it's dependencies is newer than foo.a
But what if you remove a .c file?
As build systems like make don't capture a fingerprint of the names of the inputs of a built (let alone the hash of their contents) it's very hard for them to deal with that case correctly.
Correctness is important otherwise your trust in the incremental builds quicky erodes and you start doing clean builds all the times you get an error, just in case.
The blog post [0] also contains arguments against checksums: Sometimes building a target has side effects. Checksumming every output after building it is somewhat slow. Checksumming every input file before building is very slow.
What matters is keeping track of the actual dependencies and Redo does indeed save that knowledge in a database that gets consulted between runs.