If memory serves me right, atleast the European PSP version of "Ys - Ark of Napishtim" has just got a completely regular subtitle format for the FMVs. (You know, just a completely normal text file for each language and FMV with the timing info and the subtitles).

So atleast one company has used very simple subtitles that can be quickly edited.


Another option, if a game doesn't feature subtitles at all would ofcourse be to demux the PMF streams into its respective audio and video parts, to then re-encode the h264 (movie) part of the FMV with subtitles overlayed on the actual movie itself, to the mux the Audio and Video back together.
[edit]
Forgot to mention that if the game already has subtitles in some other format, you would ofcourse probably want to try to disable/blank them out if you can't edit them (or if you're somehow technically limited by space, font, timing or something else and you just can't use them for what you want printed on screen).