*nod* for our purposes even Theora is "good enough" to put pretty pictures on the screen; we're not super concerned with the ideal codec, as much as making sure that people can actually get access to the media files we have -- the binary "works" / "doesn't work" is more important.
That's a good point. All things being equal, Theora would be more bandwidth-hungry, but thinking about that now probably counts as premature optimization. :)
Regarding web browsers: our most popular browser, sadly, is IE8. IE9, IE7, and Firefox 3.6 are all still in the top 10 with really significant numbers of pageviews. I think all these browsers will work with Cortado, though, which is one of the TMH player options.
So, on the web we could probably get away with doing free-codec-only playback, at the expense of a lower-quality experience for IE9 and Safari users (which total around 10% of traffic, or about 2 billion pageviews per month).
For mobile, I can't imagine this fixing itself all that quickly. As your tests show, good WebM playback isn't solvable in software on most of the current generation of handsets. People will need to buy new devices to make it really work.
Quick link to the traffic stats: http://stats.wikimedia.org/wikimedia/squids/SquidReportClients.htm
-Ian