"it's impossible to prove a negative" is a simplification. A negation is just the oppositive of an affirmation. If the affirmation is "there is an element E of an infinite set S that satisfies property P", the negation would be "there is no E in S that satisfy P", which would make proving by enumeration require checking every element of an infinite set, which is impossible. But other forms of proof might be possible.

The set of US patents, however, are not infinite and, IIRC, is also public. That said, IP laws are a mess.