Use software and functionality from 20 years ago
Using software from 20 years ago is the only way to surely avoid software patents.
A real case: H.261 video
A second alternative would be the reference, as a baseline, of older media compression standards, of which one can be reasonably sure that related patents are expired (or are close to expiration). One example for these codecs is ITU-T Rec. H.261, which (in its first version) was ratified in November 1988. While not competitive with today’s state of the art codecs, it’s in the author’s personal experience not that far in its performance from Ogg Theora [...] The disadvantage of this approach is clearly the use of technologies that are two decades old, but that may be at least partly offset by the commercial advantage.
Related pages on ESP Wiki
Examples of software that's 20 years old: