> A pet peeve of mind is having to "make clean" between a debug and a release build, and nearly all usages of Make have that problem, e.g. Python and bash's build system. You could say they are violating your rules because each artifact doesn't have a unique name on the file system (i.e. debug and release versions of the same object file.)
There are at least two ways that this problem can be addressed. One is to support out-of-tree builds, one side directory per configuration. Builds based on the autotools do this by default.
The other is to use a separate build directory per configuration within the build. My current project uses local in-tree directories named .host-release, .host-debug (including asan), .host-tsan, .cross-release, and .cross-debug. All of them are built in parallel with a single invocation of Make, and I use target-scoped variables to control the various toolchain options.
The engineer's incremental work factor to add another build configuration isn't quite constant time, since each top-level target needs to opt into each build configuration that is relevant for that target.
> I hit the multiple outputs problem
I wouldn't really classify that as a problem in GNU Make, as long as you can specify the rule as a pattern rule.
I hear you on the testing problem. Make certainly behaves as if the Makefile's correctness isn't decidable. Even if you levied the requirement that a Makefile's decidability was predicated on the recipes being well-behaved, I'm not sure that the correctness is decidable.