I can reproduce this with GNU make 3.82; however it is working properly for me with the current release candidate for the next release of GNU make, so this problem has been fixed.

This is a regression introduced in make-3.82.
make-3.81 handles this wihtout problems.

Directory names build from patterns seem to prevent wildcard expansion.

make doesn't seem to like pattern rule prerequisites that use globs.  I found no reference in the manual that states that this should be supported, so I don't actually know if what I'm asking for is a bug fix or enhancement.  Anyway:

$ find xxx
xxx
xxx/sums
xxx/sums/zzz.md5
$ make -rd -f x.mk xxx/md5
Reading makefiles...
Reading makefile `x.mk'...
# the following are my two debug printfs
-> parse_file_seq %/md5
-> parse_file_seq %/sums/*.md5
Updating makefiles....
<--- snip --->
Updating goal targets....
Considering target file `xxx/md5'.
 File `xxx/md5' does not exist.
 Looking for an implicit rule for `xxx/md5'.
 Trying pattern rule with stem `xxx'.
 Trying implicit prerequisite `xxx/sums/*.md5'.
 Trying pattern rule with stem `xxx'.
 Trying implicit prerequisite `xxx/sums/*.md5'.
 Looking for a rule with intermediate file `xxx/sums/*.md5'.
  Avoiding implicit rule recursion.
 No implicit rule found for `xxx/md5'.
 Finished prerequisites of target file `xxx/md5'.
Must remake target `xxx/md5'.
make: *** No rule to make target `xxx/md5'.  Stop.

... the problem being that the wildcard expansion takes place in read.c:parse_file_seq, when reading the makefile.  That doesn't find any file matching the %/... path, so it leaves the wild card as is, and later after the stem-replacement, make looks for xxx/sums/*.md5.