Actually, I just recently upgraded to MEncoder 1.0rc1-4.0.3 and also downloaded the most recent DLL stuff from the mplayer website, and I'm still having the same issues. Not sure how you got a more recent version...are you using one from SVN?
I'm on an Ubuntu Dapper system, btw. Not really sure if that makes a huge difference or not.
I haven't actually tried encoding a "small" video yet, I've mostly been attempting on hour-long TV shows (well 45 minutes without commercials).
Yea, it does seem like there's something in the video file that makes it hiccup. I've come to realize that it's not actually random places in the file, it's almost always the same place (for this particular file I'm doing, 30%-ish).
I'm going to try tinkering around with a few more things here, and if not I'll PM you some more info.
Thanks for all your help, btw