What is the state of the art for vocal elimination/reduction?
Some recent ideas (2-3 years old, I haven't followed recently):


Design an elaborate generative model of the spectrogram of music signals, combining a non-negative mixture of a small set of background frames (models the background music) + a harmonic comb filtered by a non-negative mixture of smooth basis functions (the source filter model of the lead instrument), with constraints on the pitch transitions. Estimate model parameters from the audio clip. Use Wiener filtering to resynthesize the background music/vocals from the estimated spectra. See A musically motivated mid-level representation for pitch estimation and musical audio source separation by Durrieu et al. Such Bayesian approaches can be made more complex ad nauseam, by integrating prior knowledge about note transitions/durations - at the cost of increasingly hairy inference procedures. Demo time!
Techniques inspired by background subtraction in video analysis. The idea is that the accompaniment (especially in "bland" pop music) is invariant by a translation of a few bars (the duration of the "loop" or "riff") - while the vocals are not. Once the structure of the piece of music is known and can be described in terms of repeated groups of bars (a well-studied topic in itself), one can take the median of translated versions of the spectrogram to suppress the vocals. See REpeating Pattern Extraction Technique (REPET): A Simple Method for Music/Voice Separation by Rafil &amp; Pardo. Demo time!


In the commercial space, you can download a trial for ADX Trax.