To me make's behavior seems correct.

Possibly you've missed the difference in behavior between explicit rules with multiple targets and pattern rules with multiple targets.  An explicit rule with N multiple targets is identical to writing the same rule N times, once with each target.  So this:

foo bar: ; echo $@

is identical to writing this:

foo: ; echo $@
bar: ; echo $@

This appears to be what you want.

However, pattern rules are different; see http://www.gnu.org/software/make/manual/make.html#Pattern-Intro

A pattern rule with multiple targets tells make that ONE invocation of that recipe will build BOTH targets.  That's why you don't see both the /host and /target generated: make invokes one of them and expects the recipe to build both, so later when the other is listed as a prerequisite make thinks it's already been built.

You have to write your pattern rules like this then it should work as you expect:

%/host:
        @echo $@
%/target:
        @echo $@

If I've misunderstood the situation add a comment with more detail (maybe a simpler test-case) and I'll re-open this bug.