I'm thrilled to be able to report that the new release of Opera, 10.5 (Windows only for now) has pretty decent Open Video support.
I did run into several problems, like scrubbing back and forth being prone to video errors and not handling application/ogg, but overall I'm very pleased to see another Ogg(Theora+Vorbis) implementation released.
After I've used it for a few weeks I'll try to report back on any other findings.