Format Factory works wonders in my experience. It works with mkv with soft subs! I made a tutorial
here. You have to use version 1.90 if you want custom settings. It's also free and you can grab it
here.
I've tried PSP Video 9, Xvid4PSP, and Videora with no luck when it comes to mkv with subtitles (softsubs).