Here is an even simpler Makefile which shows the problem. It is a stripped down version of the original I submitted, and makes little sense in terms of what it echos
-----------------------------------------
binary: binary.tmp
        @cp $^ $@ ; echo Install $@

.INTERMEDIATE: binary.tmp
binary.tmp:     lib
        @touch $@ ; echo Link new binary in temp place

lib:    obj
        @if [ ! -e $@ ] ; then touch $@ ; fi ; echo $@ is up to date

obj:
        @touch $@ ; echo Compile language file
-------------------------------------------------
run make once, to build 'binary' 'lib' and 'obj'. Then touch 'obj'. If you run 'make' again it echos "lib is up to date", but if you run "make -j2" it echos "lib is up to date", "Link new binary in temp place", "Install binary" and make itself prints "rm binary.tmp".

This problem appears to be related to the line "must_make=noexist;" around line 410 of remake.c. When an 'intermediate' file does not exist, but the rules for it's dependencies are still being run, it is too early to decide that the file must be created. If the rules end up not updating the dependencies, then you do not need to create a missing 'intermediate'.

This case is never encountered in the '-j1' case, as all rules are run to completion before make considers the file, so it never has a file in the "dependencies are being run" (cs_deps_running) state.

The enclosed makefile makes use of a number of Gmake facilities which should cut down on the amount built.
If one runs gmake, then it correctly builds and installs 'binary'. If you then touch 'language' and run gmake -j1 and gmake -j2 you get very different results
11:28:46 0 $ Gmake -r -j1
Run YACC and see if anything has changed
11:28:56 0 $ Gmake -r -j2
Run YACC and see if anything has changed
Link new binary
Install binary
rm binary.tmp

Am I misunderstanding something?

The objectives are
1) To preserve the existing binary if something goes wrong in the build.
2) To not rebuild the binary only because a shared library
implementation file (.c) changes. If an interface file changes (.h) that is a different matter.
3) Some files are automatically generated, if they are the same as previous ones then reuse previous object files.