I don't see why decidability should render them incomparable.
Exactly, they are macros that can only be invoked via some weird implicit entry points. Proper macros could be used very much in the same way, of course, if the compiler recognizes their output correspondingly. You could, for instance, use macros to generate traits/type classes to enhance overloading. Why someone would prefer this code generation to be so implicit, I don't understand.
> I don't see why decidability should render them incomparable.
Of course you can compare them if you want to point out that particular difference. But if you claim that templates are more powerful, the obvious answer is: Sure, because they're not type safe. Templates simply aren't a type system extension, they're more like macros.
Could you elaborate in which way C++ templates are not type-safe? Does the upcoming concepts feature alleviate any of it?
C++ Templates are not type safe because they need to be evaluated before you can make any statement about their successful, correct application. This evaluation might not terminate. Macros habe the same issue, of course, but they explicitly give you a Turing-complete programming language so it feels more natural.
You might want to consider a setup where the library author is not the same person as the library user. Don't you think it's important that the former sees and not the latter? That's why linker errors and compiler errors and template errors are not equal. Also, if you make an error in a template or its instantiation you might not even get an error but an infinite (i.e., maybe aborted) computation. If you don't see the difference between these things, I cannot help you.