This is being posted here so I have something easy to look up when I need to do it over again, but using FFMPEG 0.5.x, you can easily convert any playable movie to a Nokia N9x (N95, N96) compatible MP4 format file with the line:
(ffmpeg | ffmpeg.exe) -y -i [input file].[extension] -f mp4 -vcodec libx264 -level 21 -s 320x240 -b 768k -bt 768k -bufsize 2M -maxrate 2M -g 250 -trellis 1 -refs 3 -keyint_min 25 -acodec libfaac -b 128k [output filename].mp4
Which converts any playable video to a compatible (-level 21), correctly sized (-s 320x240) MP4 based video file with AAC audio (-acodec libfaac -b 128k) that doesn't crash the RealPlayer version on phones in Australia/New Zealand because the buffers and bitrate are cool (-b 768k -bt 768k -bufsize 2M -maxrate 2M).
The other options are entirely optional, but the -g 250 & -keyint_min 25 are recommended if you have a PAL based input stream and would like to be able to fast forward and rewind your video using the funkey buttons on the N96.