>There may even be enough mechanism in our BSD make to do this, though
>the syntax is so twisted into obscurity that I'm not sure I can figure
>out how it might work....

Not quite the same thing, but I have an autodep.mk, which adds -MD to 
CFLAGS and gathers the *.d files thus produced into .depend.
This does not solve the problem of foo.h no longer being relevant (or
existant), but for the most part dependencies are kept up to date
for very little effort.  Sure beats running "make depend" on a large tree.

--sjg