Following simple test no longer works with 3.81beta2 and cvs snapshot 20050301:

$ touch foo
$ cat Makefile
TARGETS = foo foo.out

.PHONY: all

all: $(TARGETS)

%: %.in
    touch $@

%.out: %
    touch $@

make-3.81beta1 works as expected:
$ make-3.81beta1
touch foo
touch foo.out

make-3.81beta2 (and make from cvs) breaks:
$ make-3.81beta2
touch foo
make-3.81beta2: * No rule to make target `foo.out', needed by `all'.  Stop.

Next time make completes the job:
$ make-3.81beta2
touch foo.out