What they have in common is that it's in "also builds" logic. The natures of two problems are quite different.

Ooh, this is complicated. First, the change which triggers this regression (2005-03-04) is correct, it just uncovered other bug(s).

Make chooses built-in rule because the user-provided one matches only via intermediate file ('foo.h'). The fact that make thinks 'foo.h' is intermediate even though it was just built as part of 'foo.c' is a bug. At the moment, after building 'foo.c' we enter 'foo.c' as a target and mark that it also builds 'foo.h' but we don't make 'foo.h' a proper target.

The nasty part is that all this logic depends on the order in which things are built. If, for instance, I change

all: foo.c foo.o

to be

all: foo.o foo.c

the user-provided rule will match because we first try to build 'foo.o' and now both 'foo.c' and 'foo.h' are intermediate and the built-in rule is not any better than user-provided anymore. I would imagine this can change from build to build with -j.

Well, second sample demonstrates already fixed bug with intermediate goals, so please ignore it.

Just to make things clear, first sample is expected to work this way:
$ make-3.81beta1 -n
cp foo.in foo.h
cp foo.in foo.c
echo foo.c foo.h >foo.o

But now make behaves differently:
$ make-20050503 -n
cp foo.in foo.h
cp foo.in foo.c
cc    -c -o foo.o foo.c

Following simple test (which worked up to 2005-03-01 snapshot) no longer works starting with 2005-03-03 snapshot and up to latest cvs (checked 2005-05-03):

$ touch foo.in
$ cat Makefile
all: foo.c foo.o

clean:
    rm -f .o .h *.c

%.h %.c: %.in
    cp $< $*.h
    cp $< $*.c

%.o: %.c %.h
    echo $+ >$@

$ make-20050301 -n
cp foo.in foo.h
cp foo.in foo.c
echo foo.c foo.h >foo.o
rm foo.h

$ make-20050303 -n
cp foo.in foo.h
cp foo.in foo.c
cc    -c -o foo.o foo.c