I haven't done much myself with mp4 but Im guessing ffmpeg and ffmpegx handle it, and they're free.
QuickTime Pro is like $29 and does have a few nifty features including the completely one-click encoding for video iPod and other common video standards.
iMovie (part of the $79 iLife 05 suite which has a bundle of really good apps) also does mp4 just fine. And with Quicktime 7.0.3 (non-Pro even) it directly supports the export to video iPod option, so you don't have to pay $29 + $79 if that is your goal.