Theora is not exactly mediocre, it just isn't the best. But the "best" is expensive to license, and Theora is a reasonable substitute that is completely Free.
People complain about the extra CPU power it takes to decode Theora, but if I have to choose between paying extra for a more-powerful CPU or a patent license, I would choose the former. At least I can make use of the more-powerful CPU when I'm not watching videos of cats flushing the toilet.
Surely more CPU power often equates to shorter battery life. Which really is very important to most people, considering just how badly batteries still suck.
So personally if it's a difference of battery life, I'd choose the one that uses less power and gives me more time.
If you are watching video constantly, then this is a concern. If your phone is mostly sitting in your pocket waiting for the GSM signal to wake it up, then it's irrelevant.
(And, I have a portable device that plays arbitrary video formats just fine on a rather-big 5" screen for a whole transatlantic flight; 7-8 hours. So the current technology is more than adequate, H.264 or not.)
People complain about the extra CPU power it takes to decode Theora, but if I have to choose between paying extra for a more-powerful CPU or a patent license, I would choose the former. At least I can make use of the more-powerful CPU when I'm not watching videos of cats flushing the toilet.