The problem with MP3's and other complete song formats is the fact that every track has been combine together to form a single track. The only way to truly remove vocals is to get the original multi-track (not. easy.) and remove the vocal tracks from it.
Otherwise Audacity's vocal removal option is about as good as it gets. It won't work on every song either. The vocals tend to be center panned (both left and right channels) in music after is has been combined, so Audacity does the best job it can removing what is there without mutilating the track.
The vocals will always be there a little, but if you intend to use it as a karaoke track or to put it over something that has sound of its own, it should work.
Most vocal removal will...