After some trial and error, I found that keyframe interval must be set to one.
Here a command that is working for me (fps, audio and video bitrate can be set higher or lower if needed):
Code:
mencoder Infile.avi -ofps 25 -vf-add scale=160:128 -vf-add expand=160:128:-1:-1:1 -srate 44100 -ovc xvid -xvidencopts bitrate=480:max_bframes=4:quant_type=h263:me_quality=6:max_key_interval=1 -oac lavc -lavcopts acodec=mp2:abitrate=192 -o Outfile.avi