Karaoke discs are your best bet
The quality of these nowadays is really very good and unlike the old days when the discs were REALLY expensive you can simply download karaoke backing tracks on a "track by track" basis for iTunes, Amazon etc. if you want to stay legit
YouTube is also awash with them and there are lots of tools to "rip" the audio from YouTube vids