This is more of a comment than an answer, but the fact that point compression is patented is utterly ridiculous. In essence, it's patenting the process of storing point (x, y) by storing x, and the using y = f(x).
Another thing that's interesting, regarding the 'if you use an implementation provided by someone else, you're fine' argument:
At least one hardware security module provider, which includes an ECC implementation, will not guarantee people who use their modules against patent claims. That's food for thought.
Of course, it's also important to note that in some countries (like Japan, iirc) ECC is completely unencumbered, and that many of the other patents only apply in the U.S.