Are these videos primary mkv or consist of other various formats? cause I know a great mkv to mp4 converter that all it does is remux the audio and video files so a hell of alot less time but this only works for mkv files.
XenonMKV ---> http://xenonmkv.ev98.net/
He specifically made this app for 360.
Bencos ---> http://goo.gl/ER5gE
He originally made this for anime but it has other setting for movies as well and he wanted it to have ease of mind for user. I use it for all my movies and it's absolutely great!