We didn't use it in the end, since I didn't have time to burn enough of my collection to disc.
I ran the karaoke from my laptop using PyKaraoke
You're right about CD+G. It uses an interleaved method of writing the data, given that audio cds have an error-correcting feature and don't get thrown by the extra data. There are several programs that can burn CD+G, providing your drive supports disc-at-once writing.