OS: Windows 7 Ult. 32bit
Latest version of Sony Vegas 9.0
Note: I have already tried uninstalling and reinstalling. No luck.
Well, I haven't seen it as bad as this.
If you have good output on other formats, I would check the export settings for .MP4 and make sure that you have the bitrate set high.
If all else fails, export to a good format and use Handbrake to transcode to MP4.
I'm using Vegas 9 with K-Lite codec pack on Windows 7 x86 and have no such troubles. Make sure to select MP4 during setup when prompted which components you wish to install.