Microsoft has a patent on the openly-spec'd FAT filesystem and are still pursuing royalty agreements with distributors of FAT code:
http://arstechnica.com/microsoft/news/2009/02/microsoft-sues...
If software patents were removed from the picture in the USA, H.264 would cease to be a proprietary algorithm.
Edit: I'm updating this because the reply markers are slowed down to flamewar levels. :)
Re: consent of the patent holders, this is guaranteed by the MPEG LA but only in return for royalties paid. You need their permission, which is granted only by paying the royalty.