Another way would be to try to use the fact that a lot of vocals are mono and centered.

Right, that's how vocal-removal algorithms work. They do phase cancellation between the left and right stereo channels. And it works surprisingly well on some songs, as long as you can stand it erasing a lot of the instruments along with the vocals. If you want to hear how it works on MP3's, you can get WinAmp plug-ins which do this. I've played with them, and they are quite interesting, if not universally useful.