Years ago I had tried several that never worked that well.
The thing is, these programs usually have you select a certain sample in the audio as the 'source'.. and then it removes all sounds from that frequency range for the entire file. (you select a portion of the wav that is dominatly vocals.. then it removes the frequencies from the entire file that are present in this selection)
The good ones allow you to change the level of remove with a slider as well.
The problem is.. for complete removal, it also removes those same frequencies from the music itself making it sound shallow and virtually un-usable.
The only program that I can remember that worked the best was called Cool Edit Pro(which is now called Adobe Audition). It is not made solely for this purpose and you'll find the $400 price tag not worth it for what you are doing.
If you know of any good musicians with recording equipment that would probably be your best place to start.