Fixed and merged. The issue was that Makefile.depend only contained the
dependencies for the value of STATE_VAR_BYTES that was current when it was
generated, and hence dependencies could be missed when switching to a different
value of STATE_VAR_BYTES.

Steps to reproduce:

In src/search directory with clean working directory:
$ make distclean
$ rm -f downward.{1,2,4}
$ X=90ed8ac11e01
$ Y=3cb644513efe
$ cd ..
$ hg update $X
$ ./build_all
$ hg update $Y
$ ./build_all

The buildbot reported some problems with compilation; Erez later saw the same
problem. The problem only occurred with the "downward.2" variant and disappeared
after a make clean; make cycle, which indicates that something might be wrong
with the dependencies.

Indeed, our dependency generation strategy is essentially blind to the
STATE_VAR_BYTES variable, so it's very much conceivable that things can go wrong
there.