At the moment I get the "install flash" message on Youtube videos a disappointingly often amount of the time. Weirdly I've had the experience where embedded HTML5 Youtube videos will play, but they won't when I click through to watch the full-size video on Youtube.
Here's a tip I've found useful: if you run into the "Install Flash" message, you can usually edit the URL to play in HTML5 instead. Change "watch?v=" to "embed/" (and if there are other querystring arguments starting with an ampersand, just strip them off). There are a few YouTube gateway sites that do something similar, but I remember the 'embed' trick better.
Am I missing something or do I just not watch enough YouTube to come across the problem you are describing?
If you want a short term solution, I usually just swap to an iPad user agent string if I want to force html5 video.