The implicit rule search algorithm from the manual, step 5c:

"Test whether all the prerequisites exist or ought to exist.
(If a file name is mentioned in the makefile as a target or
as an explicit prerequisite, then we say it ought to exist.)"

But this is not what the implementation of "ought to exist" does.  It checks whether the prerequisite has been entered as a file.

The requirement that the prerequisite be marked as a target was removed in bug #17752 in the name of making implicit rule search less sensitive to random side effects from other things going on in the makefile.  However, I'd argue that the change has hardly made any progress toward that goal, since the search is still sensitive to whether other activity in the makefile has entered the prerequisites as files.  Consider this example:

test.foo:

enter-file-%: % ; $(info entering file $<)

%.foo : baz ; $(info chose $< to make $@)
%.foo : bar ; $(info chose $< to make $@)

ba% : ;

The output with the latest CVS make:

$ make -f still-order-dependent.mk test.foo enter-file-bar
chose baz to make test.foo
make: `test.foo' is up to date.
entering file bar
make: `enter-file-bar' is up to date.

$ make -f still-order-dependent.mk enter-file-bar test.foo
entering file bar
make: `enter-file-bar' is up to date.
chose bar to make test.foo
make: `test.foo' is up to date.

Maybe it would be good to implement what the manual says: flag files that were explicitly mentioned in the makefile and have the implicit rule search check for that flag.