Were the video that worked and the video that skipped encoded with the same method?
People seem to find WinFF the easiest to use.
If you are comfortable with the command line, I'd suggest mencoder:
mencoder -of mpeg -oac lavc -lavcopts acodec=mp3:abitrate=160 -af resample=44100:0:0 -ovc lavc -lavcopts vcodec=mpeg2video:vbitrate=300 -vf scale,harddup -ofps 12 -zoom -xy 320 inputfile.avi -o outputfile.mpg
where 160 is audio bitrate, 300 is video bitrate, 12 is frame rate, and 320 is width in pixels (height is automatically calculated). You'll want to change at least the last two based on the "performance" table on PluginMpegplayer.