Using Safari 5.1.2 in Mac OS X 10.6.8

I've long ago uninstalled Flash and didn't have any issues with YouTube due to being part of the HTML5 opt-in. However lately I'm noticing a lot of videos aren't playing claiming my browser doesn't recognize any of the video formats. Going to the HTML5 YouTube page shows it's active and that the browser supports H.264 and WebM (I have Perian installed).

So what's going on? I've also tried Firefox 6 and it claimed to need a plugin which it was subsequently unable to locate.

Even after turning off HTML opt-in I'm not being prompted to install Flash, so it doesn't appear the videos are flash-wrapped either.

Here's a random sample that gives me this error: http://www.youtube.com/watch?v=gnxo0Ffp3KQ&feature=related

Damn, I don't hate many things, but I despise Google. They make Microsoft (at the worst points in the history) look like infallible angels.