.mp4 is the video and audio container. Many different formats can be used inside the container.
Use VLC to open the file. Tools - Media information (Ctrl + i) - codec to see what the video and audio are encoded as.
You can also use VLC and Convert/Save and re-encode the video and audio in new format that can be opened by blender.
E.g. did this just now starting with mov*.mod files which contained mpeg 1/2 video and ac3 audio. Chose profile Video - H.264 + MP3 (MP4) Converted to .mp4 containing H264 mpeg4 avc video and mpeg audio (with same resolution video 720x576 25frames/s audio changed from 48kHz to 44kHz 32bit audio). Blender opened that format.
