I reported this as http://bugs.debian.org/584281 back in June,
but only recently got the advice to report it upstream instead.
I'll just quote my original description:

If you let makedepend generate dependencies for multiple .c files in
different directories, and two of them do

  #include "foo.h"

and expect that to mean the foo.h which is in the same directory as
the source file, makedepend will pick one of the foo.h files (and
whatever it includes) and apply as dependencies to both .c files.

To see the problem, do:

mkdir a b
echo '#include "foo.h"' > a/foo.c
echo '#include "foo.h"' > b/foo.c
echo '#include <stdlib.h>' > a/foo.h
echo '#include <stdlib.h>' > b/foo.h
makedepend -f - ?/foo.c

You will see among other things these two dependencies:
a/foo.o: a/foo.h
b/foo.o: a/foo.h # incorrect; should be b/foo.h

This bug seems to exist in all makedepends I have tried. I suppose it
comes from the optimizations mentioned in the manual page. I really
don't like it, because it will silently generate Makefiles with bogus
dependency graphs in them for what (to me at least) looks like pretty
normal source code. Such Makefiles are dangerous -- especially when
you trust them, because you let the standard tool makedepend generate
them.

If it cannot be fixed, this bug should be mentioned in the makedepend(1)
man page.