I believe you can encode paradoxes in C++ templating.
Something about two specializations which are mutually impossible because they reference eachother. So you can say:
A is of type T <=> B is not of type T
B is of type T <=> A is not of type T
Where <=> is if and only if.
In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.
Note that "a template for which no valid instantiation is possible" is actually ill-formed, no diagnostic required.
That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.
In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.