Really? I've never had problems converting softsubbed H.264 MKV releases for my PSP.
How do I do it? Simple, I use XviD4PSP. Despite it's name, it converts basically everything for multiple portable devices (in order for it to handle softsubs, you need to check Autoload VSFilter in CCCP settings page 2).
Also, too bad Mentar isn't encoding this. Now we're getting an upscale at 350 MB, which is pretty ridiculous.