I'm noticing this in my Mozilla build, which uses -Wp,-MD,.deps/filename.pp to track dependencies. If I touch a header file, the source files which include it do NOT get rebuilt as they should. This broke sometime since -69. I can provide the generated dependency files if that would help.
There is just one issue I'm aware: the goal in the dependency file has full pathname in front of it instead of just basename.o. This should be fixed in cpp-2.96-76, but there is one gcc driver bug in that version which will be fixed in gcc-2.96-77. Can you check if that is the reason why dependencies don't work right for you (ie. can you replace /some/strange/path.o: some dependencies with path.o: some dependencies in the .pp files?).
I haven't had a chance to check it for sure yet, but this sounds like it's the problem. I am building in a separate object dir, and the path to the .o in the .pp file is actually the path to the source file with .cpp changed to .o, so it was referencing the wrong location.
This is fixed now.