I know this thread's a bit old, but need to throw in my two cents. The issue is definitely network related, but not with bandwidth or buffering. I have exactly the same issue, exactly the same symptoms.
What you'll see when a freeze happens is that first your audio bitrate will drop to zero, but the video will continue. The video then gets too far out and stops, then the audio picks back up, rejoins the video position and the whole thing sync's back up. This only seems to happen with particular file formats (i.e. avi, improperly packaged mp4). The TSMUXER fix (used by PMS) is a great workaround, and it creates a file that the PS3 is most comfortable with. Searching, FF and RW are badly impacted tho.
Oddly enough, those videos that freeze like this over media server play fine off of disk or from hd. So the issue still seems isolated to network.
I keep hearing how it's a bandwidth issue. It's not. I can play AVCHD video (15000 mb/s video, 5.1 surround audio) over wireless media server perfectly, but a 950 mb/s stereo xvid video will freeze. Ever notice how mp3 audio files will freeze in a similar way? That's not bandwidth!
Steps to take: 1) force the PS3 to decode audio at 44,100 k (as opposed to 48000). You'll notice your mp3's will play better, and see a big improvement in your avi (including xvid) files. 2) MP4 video is actually the best way to go. But don't go creating a video using the PS3 as the target device - it most likely won't work, or if it does play, it'll stutter like mad. Do a generic default mp4 target with aac audio. You'll get an MP4 that will play flawlessly, with search, FF and RW still working, and if you keep the audio to stereo, it'll play great on Xbox as well.
This whole thing is a flaw in the PS3, not with PMS. And it's been going on long enough. Sadly, it was more important for Sony to remove the OtherOS feature (the reason I bought PS3 instead of Xbox in the first place) than to fix this huge defect. And they're still silent.