Here is a site that uses the Windows Media Audio format to playback Karaoke tracks with the Audio & Graphics combined...
Easy Karaoke
It use Windows DRM (Digital Rights Management) to protect the original recording, but utilises the WMA Software...
I do not no what software they use to convert CD+G to WMA
But i'm sure it's available somewhere... and in comparrison to .MPG File size to WMA File size... I know what one I'd choose.
I hope this os of help to you