Super NEVER works for me, but I think I have worked out a solution for almost all S60 phones if you want to use the Real Player.
You need both an mp4 encoder (Super/xilisoft/imtoo/whatever) and Quicktime Pro.
You will have to do 2 conversions because QT Pro is fussy with video codecs but it gets the settings EXACT for Real Player.
1st convert your video with your mp4 encoder into an mp4 file. The settings you can set to auto, they dont really matter.
As long as Quicktime can open them the video you just made (or already can play it), you are ready.
In Quicktime, export the file.
Set the file name and on the export tab, choose Movie to MPEG-4.
Then click Options.
Use mp4 as the file format.
Use mpeg4 improved as the video format.
Image size should be QCIF
400 kbps (640 max)
Check the box for preserve aspect ratio and letterbox.
15 frames per sec / automatic keyframe. (Feel free to make this higher, but I didn't get it to play smooth)
Be sure to make the audio show up. Defaults should be fine.
This worked on the 6682 I currently have in my possesion. These settings should work for 3250, E50 and 5500. Also should work for devices going backwards to the 6600.
If you have the N70, N72, N90, E60, E61 or E70, use CIF or QVGA instead.
If you have a Symbian 9 based N-Series (N71, N73, N80, N91, N93), try using h264 as your video format.