Why do you need to convert to mp4 for karaoke?

Sounds like you should use a transcoder instead of converting your source file down to a lower quality formats just to support weaker devices. For your iphone/ipad, AirVideo works well. Keep your original karaoke videos at the original quality (MKV or VOB) and weaker devices can still play using a transcoder.

Here is the format that is compatible w/ ipad. Note that the audio has to be 160kbps or lower.
iPad/iPad 2 Supported Video Format
H.264 video up to 720p, 30 frames per second, Main Profile level 3.1 with AAC-LC audio up to 160 Kbps, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats;
MPEG-4 video, up to 2.5 Mbps, 640 by 480 pixels, 30 frames per second, Simple Profile with AAC-LC audio up to 160 Kbps per channel, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats;
Motion JPEG (M-JPEG) up to 35 Mbps, 1280 by 720 pixels, 30 frames per second, audio in ulaw, PCM stereo audio in .avi file format.

Download the AirVideo app. It can transcode on-the-fly or convert to mp4 specifically for your ipad for you. Transcoder is something that takes the original source and convert live to a source that works for your device. This is useful especially when you have different devices feeding on the same source - instead of converting a video file to 5 different formats for 5 different devices, you can just have 1 source and the transcoder will kick in and make sure all 5 of your devices can play.

Think about the "transcoder" has the translator. Say you have a book written in English and you have 3 students that can't read English - they read Vietnamese, Spanish, and French. Instead of reprinting the book to 3 different languages, you hire a translator that can speak 3 languages and read the English-version book to each of the 3 students in their own language.