The problem is that not all mp4 files are the same. MP4 video file is basically a container of video and audio codecs just like .AVI or Matroska. This mp4 file with the codecs below plays fine on WMP 12 without any 3rd party codecs/plugins.
If you want the your mp4 files to always have the codecs in the picture above, just download Handbrake
and convert all your videos using "Normal" Profile with an mp4 file extension. (note "high profile" doesn't work with WMP12).