Sure, probably the easiest and most efficient way is to frameserve the original file with AVISynth using VSFilter's textsub or vobsub functions to add the subs. Re-encoding causes a loss in quality at the best of times though and subtitles are not easy to compress.
If possible I would suggest leaving the subtitles as a seperate stream.