If it's only twice as big it's only going to take ~ twice as long though so it depends on the picture. Though in this case could PS3 Media Server provide static re-encoding for selected folders where in the background it'll begin re-encoding poplar viewed files.
Another thing I was going to say is regarding re-encodes of subtitles, is to not possible to simple have the mkv/ogm etc transcoded into mp4 etc then the only re-encode the blocks around the subtitles? This would speed up subtitle re-encodes greatly. Also there are moments especially during fast scenes when you are unlikely to see subtitles, could these moments not be transcoded? This would help prevent running out of buffer in the majority of situations.