After some researches I finally found a mencoder string capable to encode mp4 high quality videos from avi files compatible with Nokia mobile devices (Tested on 5610 XpressMusic and N95 but should work on other models).
After mplayer installed just run:
$ mencoder -of lavf -lavfopts format=mp4 -oac lavc -ovc lavc \ -lavcopts aglobal=1:vglobal=1:acodec=libfaac:abitrate=128:vcodec=mpeg4:keyint=25 \ -ofps 25 -af lavcresample=44100 -vf harddup,scale=320:-3 \ -mc 0 -noskip OriginalMOVIE.avi -o MobileMOVIE.mp4
Obs. Remember that you can write a simple script to convert lots of videos at once…
Now, just upload them to your Nokia device and have fun!