Eso es lo que venimos tratando de decir desde el primer momento.
Una cosa es reencodear, que básicamente graba el video/sonido de nuevo. Cuando haces esto, te da la opción de pegar también subtítulos a la pista de video, que son los llamados "hard subs". Estos como son parte del video, obviamente se van a ver siempre, quieras o no. El tema es que esta forma es realmente lenta, y cuesta mucho que quede bien el sonido/video y que no pese una tonelada. Esto es lo que vos estás diciendo que haga.
La otra forma es, sin tocarle un pelo al video (divx/x264) y el sonido (mp3/flac), meterle en el pack (mp4/mkv/avi) además una pista de subtítulos. Eso es rapidisimo, y te garantiza mantener la calidad del original. Podés agarra un video viejo, desarmar el avi, sacar la pista de audio y video, agregarle subtitulos, y armarte un mkv que es un pack mil veces mejor. Y también a la inversa. El punto negativo es, que no toca justamente los originales, y si por alguna razón el dispositivo que lo tiene que reproducir no los soporta, no te va a funcionar.