Hi Tim. If you are using multi-track MP3's (Karaoke-version, etc.), I recommend downloading them as individual tracks and making two 'stems' mixes, one with drums and percussion, and one with all the pitched tracks. Then just transpose the pitched stem, and mix the two stems back together.
It is amazing how well it sounds as long as you don't mess with the drums' transients and tone.
But if you only have a stereo mix, then yes, you are kind of stuck having to mess with the drums. I would recommend trying a few different pitch transposers out, though. They all sound a little bit different, do better or worse job on different types of material. Do the identical transpose on the same file by all of them, then do a listening test.
Currently, because I can't really justify the full Serato Pitch 'n Time (pretty much the current gold standard for pitch transpose) I use a Mac program called Amazing X (an OSX version of Amazing Slow Downer) which seems to do a pretty good job...
But I do need to try out QMIDI, see how well that compares.