Incidentally Next Computer's Fast Elliptic Encryption, FEE, used elliptic curves, and is patented (by R E Crandell, USP# 5,159,632,27 October 1992); also, elliptic crypto is probably covered by the DH/PKP patents.
Is the FEE patent on some tweaking of it, or are they claiming anything using ECs for crypto? (Esp. DH and ElGamal analogue)? PKP claims all public key, but: a) Vanilla El Gamal crypto is covered, tenuously at best, by their Diffie-Hellman patent, which some consider to be contestable based on publication more than a year before filing. The DH patent expires in a few years as well. b) EC-based El Gamal is ever farther from DH and vanilla El Gamal (since it uses different math). It is even less likely to be held to infringe. PKP's overall claim to public key cryptography may also be weakened by several different outcomes to the current round of lawsuits. One thing that is _not_ likely to be weakened is their claim on RSA. Therefore, if you're not interested in supporting PKP's attempt to make their strongest patent the centerpiece of various Internet standards, working towards EC encryption is a Good Thing.