[Originally a comment on hacker news on 29th May]
H.264 / MPEG4 part 10 / AVC
Yes it is patented which is a definite disadvantage compared with a theoretical patent free codec but it has some real advantages.
1) The standard is controlled and defined by a collective industry group under the auspices of ISO. 
2) Most of the major players in video technology at the time took part in the standardisation so are committed to FRAND patent licensing terms. 
3) In almost all cases and commercial business models (that do not involve Free software) the MPEG-LA H.264 patent license is really very reasonable and unlikely to cause problems to an otherwise healthy business. Note that the license Google has to the MPEG-LA pool of patents while free is NOT compatible with Free software.
4) Any companies not in the MPEG-LA pool that popped up now with demands really would trolls in the original sense that they have sat under the bridge for a long time waiting for a juicy opportunity rather than being upfront earlier. I don't think that this would help them in a legal case although there is no guarantee that they don't exist. 
5) H.264 is really quite good although the latest codecs are showing what can be done with further development and processing power.
6) H.264 decoding (and often encoding) is cooked into a massive amount of existing and deployed devices in ways that cannot be adapted to VP8/VP9 by a software update.
For now H.264 is the no brainer option for any commercial system although multi codec support may be worthwhile in some cases. If you want patent free I recommend MPEG1 as I believe any patents on it should now be expired or at least expiring very soon if they were granted a long time after filing. I'm glad that Firefox has backed down and will now use the OS codecs to allow playback of H.264.
 The OOXML case shows that this isn't foolproof but in my view it is a better option than the standard being controlled by a single company even if the controlling company publishes the source code. This applied to Microsoft when they offered VC-1 as a free alternative to H.264 (there is now an MPEG-LA pool) and to Google now with VP8 and VP9 now. Google is the new Microsoft and has fully learnt the lessons of "Embrace, extend and extinguish".
 Not Free software compatible but better than nothing. And even Google's license to the VP8 patents from the MPEG-LA pool does not seem to grant Free software compatible rights.
 There is a greater risk of people popping up with claims against VP8 or VP9 as they are newer and less prominent. The MPEG-LA's call for a pool of patents has helped draw out those patent owners and many have joined the pool and reached terms with Google (although Nokia and maybe others haven't.
 Realistically for patent free greater than 20 years old is the answer so it probably needs to be MPEG1.