First message: try cancellation (harmonic, binaural, or via blind separation). The auditory system does it, there must be some reason.
Second message: there are lots of things to try! These range from things that are relatively close to human auditory processing (harmonic cancellation, binaural cancellation) to more sophisticated techniques (multiple microphones, blind separation, audio-visual cues).
Third message: to keep happy, you must choose the problem well so the results look good. Don't use high SNR: it's hard to improve things. Use low SNR: the problem will seem hard and improvements will be spectacular.
Fourth message: use missing feature techniques (next section).