Ok, I tried it out with an avi file as input. The avi file was 52 minutes duration. I imported the avi, changed format to MP4 Nokia 5700, which was the only preset with Nokia in it. This turned out to be 320 by 176 resolution. I changed this to 320 x 240 by going to Video, Resolution/Aspect and changed the second value. There are probably other presets that already have this aspect ratio, I just didn’t go explore for it.
To increase speed of encoding I changed the default to x264 HQ Turbo, which is the quick encoding setting according to their website. My 52 minute video was converted in 9 minutes and 40 some odd seconds. Plays perfectly in VLC media player. MediaInfo tells me it is 320 x 240, 15fps, 385kbps. What frames per second rate do you need for your Nokia? Is it 15 like this preset gave me?