Besides, converting MKVs to MP4 using HandBrake is pretty easy and painless.
No it isn't. Every time I've tried, it's been lossy and taken bleedin' ages. It should just be a matter of taking the content from one container and putting it in another, but it's almost never that simple.
MS should just bite the bullet and support the other media containers. I'm fed up with a chunk of my anime collection not playing on my 360 because MS are being petty about it.