How has VLC been able to play mp3s, DVDs, and other media formats natively when other players were forced to pay licensing fees, hence the need to buy media players 10 years ago?
Problem solved!
VLC is clear example of lack of patents fostering innovation.
LAME hasn't included an mp3 encoder for these same reasons, even though its FOSS software.
I always assumed the reason no one bothered VideoLAN was a combination of the fact that 1.) VLC truly has remained a non-profit project, unlike many other FOSS software that makes money via some kind of business model (ads, premium support, etc.) and (less likely) 2.) everyone loves VLC so much that even the people possibly affected by the licensing don't care because they use it themselves.
Copyright holders have formed a few broad, cross-industry associations in order to protect their rights as widely as possible. These organizations represent the combined interests of many powerful people and so are able to exert significant political influence.
There are no equivalent organizations for patents, and the numerous industry bodies that manage licensing are often very small, narrow in scope, and lack the funding to lobby effectively.
There can be damages even for no-cost software because it isn't measured by the profits or earnings from the software but by the market loss on other software profits.