I think I got it!

I'm getting REAL close to having working video on my Sony MP3 walkman.

I decided to ditch the GUI frontends and delve into the not-so-difficult world of FFMPEG on the command-line. This FFMPEG command creates working video, but stuttering audio:

ffmpeg -i (infile) -b 500 -s 320x240 -vcodec mpeg4 -ab 128 -acodec aac outfile.mp4

I believe it's because this command will create audio at 48 kilohertz sample rate if you feed in a VOB file (raw DVD video, which I was), that was causing stuttering audio. If you add -ar 44100 before the -ab argument, that should fix it. I'm just copying over the new file right now, and I'll test it.

EDIT: Same problem occurring. This time I'm trying completely different settings. I don't care about finding out what the exact fault is (I don't have time to encode all these videos many times!), I just want to find an incantation that works so I can write a GUI frontend.

I am currently trying this command:

ffmpeg -i (infile) -b 576 -s 320x240 -vcodec h264 -ab 128 -ar 41000 -acodec aac outfile.m4v

So, I've changed the video codec to h264, the bitrate to something a little more round (in computing terms, 576 is more round than 500 - it's a math thing), and the container format to m4v. Right now the actual bitrate is climbing to above 768kbps, which is non-supported by the player; we'll see if the MP3 player will play it regardless.