Наконец-то сделал то, о чём так долго мечтал: перекодирование видео. Выбрал h264, как самый универсальный: поддерживается в HTML5, в Flash, iPhone и Android. Пока что проигрывается на сайте через флеш-плеер, чуть позже добавлю HTML5 для православных браузеров.
Перекодировка выполняется ffmpeg, подробности в первом комменте. Сейчас с дефолтными настройками качество немного хуже оригинала, нужно подбирать параметры. Буду благодарен за любые советы из личного опыта.