Keep in mind all MP4s are not the same. MKV & MP4s are just containers. It's how they are encoded that is the crux of the issue.
Ideally what you could do to avoid some of the various incompatibilities of XBOX/PS3/etc. is utilize software that handles the formats/codecs correctly and sends them directly to the HDTV, avoiding the monkey in the middle problem of a arguably less flexible game system. Try the same MKV file with VLC player, for example. It's still entirely possible that you have downloaded a file using a proprietary codec which one of the 'swiss army knife' type players (like VLC or GOM) still will have trouble with out of the box. The following pages might be of use to you-
There's some excellent reading here on the blu ray format-
FWIW, Mediainfo is useful tool IME to see what's under the hood of a particular file-
Over the long run it's better to find a way to play the original file instead of converting/transcoding just to accomodate a particular standalone device. One exception might be if you cannot run adequate cables from your PC to HDTV, or need to find a way to get HD content to older SD equipment/systems, like the trusty DVD player/Sony Trinitron in my guest bedroom ;). Some HD movies/files get converted to standard DVD using the ConvertXtoDVD app.
Hello! Recently i got a 3D TV Which supports Full-HD, so i wanted to try 1080p or 720p Movies, so i downloaded a 720P Blu-ray movie, which was a .mkv which simple doesn't play on Xbox, Neither does Blu-ray, So i converted it to a mp4 file but it doesn't appear on Xbox? Is it cause of blu-ray or something? This is from PC to Xbox Streaming, also are all HD Movies that are +720p Blu-ray? Since every movie i find is Blu-ray, Can i download a normal movie and then convert it to HD and it will work? Since every ******* movie which is HD+ is blu-ray