Thanks for the ideas. I'll try some multi-pass encoding I guess. It still puzzles me why other media players handle the video properly.
EDIT: Found a solution. I first rip the dvd to the hard disk with:
Then run something like this:
mplayer -dvd-device /media/cdrom0 -dumpstream -dumpfile /path/to/uncompressed.VOB dvd://1
This will also work with x264. My new guess is that the av-delay issue I was having had something to do with reading data from the dvd drive while encoding. Maybe DMA is not working properly? But then shouldn't I notice skippy dvd playback? Who knows. The point being, doing a rip to the hard disk first, then encoding from there solves the issue.
mencoder -oac mp3lame -ovc xvid -xvidencopts "bitrate=1024" -o /path/to/compressed.avi /path/to/uncompressed.VOB