Mozilla recommends[0] WebM (VP8 and Opus) and MP4 (h264 and AAC) for good compatibility. That's why I suggested suggested having a VP8 version of the video for cases like this.

I guess OGV could be used for even better support, but it doesn't compress as well.

[0] https://developer.mozilla.org/en-US/docs/Web/Media/Formats/V...