Mencoder can do it for mpeg1, but apparently not for mpeg4. However, with two-pass encoding, the encouder should be able to make a nice version that should smooth out the problems in the fast moving parts. Mencoder supports this and it shouldn't be too hard to add to Media Converter.

Although, apparently there may also be problems in nokia 770 itself in decoding fast paced action.