Yes, it definitely can be done, although I don't know
the exact mechanism. Go to
http://www.doom9.net and
look in the downloads section. There are several
subtitle utilities there. I know it is possible to
have SVCD with permanent subtitles. SubMuxer is probably
what you need to use.