Thanks for the detailed response, and it confirms my understand of what is occurring. The videojs fallback I think would be a great solution. I was testing last night in my mods only area, and having to explain to each user the nuances of what is occurring. I'm definitely going to leave the plugin in-place but I don't think I'm going to market it hard because of the confusion that may happen amongst users, since many just expect things to "work". Absolutely not your fault at all, and obviously an issue on the end of the browsers/too many codecs out there. I'm more than willing to throw a beta version on my server as well once you go down that path, since this is something our users have been asking for, for a long time.
I'll be watching for the updates!