Sua escolha está correta. O áudio H.264 + MP3 em MP4 é suportado por quase todos os dispositivos e PCs.
Em relação às opções de busca (indexação), você deve colocar quadros-chave em intervalos regulares. De um modo geral, deve-se ter um quadro-chave a cada três segundos. A maioria dos transcodificadores possui opções de quadro-chave, quadro I ou IDR (Instantaneous Decoder Refresh), onde é possível definir isso. Outra possibilidade seria definir o tamanho do GOP , que também define o intervalo do quadro-chave.