Ваш выбор правильный. Видео H.264 + MP3 в MP4 поддерживается практически всеми устройствами и ПК.
Что касается параметров поиска (индексации), вы должны ставить ключевые кадры через равные промежутки времени. Вообще говоря, нужно иметь ключевой кадр каждые три секунды. Большинство транскодеров имеют опции ключевого кадра, I-кадра или IDR (мгновенного обновления декодера), где вы можете установить это. Другой возможностью было бы установить длину GOP, которая также определяет интервал ключевого кадра.