After a lot of trial and errors I finally settled on mencoder with these options to encode an AVI file to the optimal Nokia IT format .

This size plays full screen on the Nokia N810.

mencoder input_movie.avi -ovc lavc -lavcopts vcodec=mpeg4 -oac mp3lame -vf scale=400:240 -o output_movie.mpeg


Hope this helps for those using only mencoder.

Of course you still can play with bitrate options etc, but I left that out since not meaning to add too much.