I'm not going to post an answer, because I think your proposal is correct: "the negative fact that the (XXX) design is not...".
It would not be right to omit the second "not"; it's got to be there. The negative fact that cannot be proved is that the (XXX) design is not a trademark. It is indeed very difficult, in principle, to think of a way you might prove that something is not a trademark. You'd have to examine all the trademarks ever registered in order to prove that this design is not among them.
If you leave out "not", you are saying that they cannot prove the negative fact that the design is a trademark, which is nonsensical (the proposition that it is a trademark is not a negative fact but a positive one).
Seriously, I think you're OK. These negatives are confusing, but they work here.
On proving negatives, see
http://en.wikipedia.org/wiki/Proving_a_negative