Most HD is distributed in either WMV-HD or mkv x264. WMV-HD plays by default on the Xbox360 but mkv’s do not and transcoding 1080p can take a long time.
The thing is, you dont need to transcode the entire file, usually just the audio (360 cant play AC3 from within a mp4 container). The x264 that exists within the mkv works perfectly on an Xbox 360 and it takes nothing more than copying the video from one container to another, and re-code the audio.
You simply need:
ffmpeg -i input.mkv -vcodec copy -acodec aac -ab 192k -ac 2 -threads 0 -strict experimental output.mp4
Depending on your version of ffmpeg, you need to replace aac with libfaac.
You can also create a batch script that converts an entire directory of mkv’s to mp4′s for you.
FOR /R “in” %%D in (*.mkv) DO ffmpeg -i “%%D” -vcodec copy -acodec libfaac -ab 192k -ac 2 -threads 0 -strict experimental “out\%%~nD.mp4″
Create a text file called convert-mkv-mp4.bat and paste this line inside, when you run it the script will look inside a directory “in” and outputs the mp4′s in a directory called “out”. You will need to create the two directories yourself before running the script or errors will ensue 
If you need recent win32 ffmpeg builds, you need to check my ffmpeg win32 autobuilds page.