I had some time to revisit the problem and a workmate gave me the tip to use "process monitor" from sysinternals to figure out which file is missing.
Lo and behold it worked! It turns out that Visual Studio insists on linking against a bunch of libs even if the app does not need it. Due to an unfortunate (I guess...) chain of events, one of the default library paths disappeared from Visual Studios global settings, so VS couldn't find this lib anymore ("coredll.lib" in my case).
This didn't affect the final output, because this lib is not needed at all, but it still triggered a relink every time.
There are two possible fixes:
1) Restore the path to this lib in the global Visual Studio settings
2) Use "$(NoInherit)" in AdditionalLibraries to get rid of the unneeded lib.
I used solution #1, because #2 needs to be done for each configuration of each project because can't be done via Property Sheets.