One suggestion: Although it's an extra click, maybe try out a "search artist only"/"search song only"/etc... approach? I was searching for the band "everything everything," which only turned-up results with songs with the word "everything" in it. That or tweak your results ranking mechanism to favor exact matches?

Keep up the great work.