If you don't mind me asking, what transcoding engine are you using when you watch your videos on the PS3? MEncoder, AviSynth/FFMPEG, AviSynth/MEncoder, or Tsmuxer? When things work out for me, Mencoder works usually pretty well, but when I have problems with a particular video with an oddball set of subs AviSynth/MEncoder tends to work in it's place.
Also, have you tried lowering the transcoding buffer to about 100-200 megs to see if it's a memory/virtual memory output problem? And, if you're using the PS3 in wireless mode, keep in mind that the files that would normally work without transcoding operate at a higher bitrate (in some cases anyway) than that of the transcoded file.
Another thing to also consider would be limiting the overall bitrate for transcoded media (8 to 15megs over wireless) so the PS3 can properly receive it. If it's on a wired network, then you'd need to see if your router is being overloaded by the information it's transmitting.
ACK! I totally realized that this may not help, but it's just a troubleshooting walk through that I normally go through when I have problems similar to yours.