We're talking about minimum message length, and the minimum message of NOT NOT P is simply P.

That's what i said. But you also said that NOT P takes more bits to specify than P. You can't have it both ways.

You don't understand this point. If I've already communicated P to you -- do you need any further bits of info to calculate NOT P? No: Once you know P, NOT P is also perfectly well defined, which means that NOT P by necessity has the SAME message length as P.

The abstract syntax tree for "x != 5" is bigger than the AST of "x == 5".

You aren't talking about minimum message length anymore, you're talking about human conventions. One might just as well reply that since "No" is a two-letter word that means rejection takes less bits to encode than the confirmation of "Yes" which is a three-letter word.

I expect, though I haven't verified, that the earliest, simplest compilers generated more processor instructions to compute "x != 5" than they did to compute "x == 5"

If we have a computer that evaluates statements and returns 1 for true and 0 for false -- we can just as well imagine that it returns 0 for true and 1 for false and calculates the negation of those statements. In fact you wouldn't be able to KNOW whether the computer calculates the statements or their negation, which means when you're inputting a statement, it's the same as inputting its negation.