I was in the karaoke business before. There's nothing like looking for the instrumental versions (the so-called "Side B") of the songs you want to convert.
I don't know where you intend to use the instrumentals, but also consider looking for their MIDI equivalents. A lot of them are downloadable from the internet.