Visual Hub does a great job encoding these files using the AppleTV setting in the iTunes tab. My only gripe is that the 360 does not recognize any 5.1 audio with the .mp4 container. I can't seem to find any Xvid/Divx HD encoders so that I can keep the surround sound. After all,HD isn't HD if your neighbors aren't complaining.
I have found a way to re-encode a .mkv file to be compatible with my ATV, iPhone and with my Xbox 360 over Connect360 (but 5.1 is still lost)
First in VisualHub, passthrough the audio (open VisualHub, click Advanced, and in the field 'Extra FFMpeg flags:', select 'copy original audio track (passthrough). This tells VisualHub to skip re-encoding the audio), but re-encode the video. For example iTunes, optimized for All, Go Nuts with H.264 box checked.
Then with the finished file, open in Quicktime and passthrough the video, re-encoding the audio from 5.1 to stereo. For example Export to MPEG-4, options: File format - mp4, Video Format - passthrough. Audio - AAC-LC.
2-step process but doesn't really require any more time as the audio and video are done separately instead of together.
This is ripping my .mkv 5.1 files to stereo .mp4. You do lose the 5.1 but at least it works