The DMCA provides the clear guidelines you're referring to. Grooveshark also falls back to the DMCA and their willingness to comply as evidence that they are legal.

I think the biggest issue for music startups (disclaimer: I used to work for one) is probably that the startups that try to do it legally and correctly are still competing against the ones that border on being illegal, or are straight-up illegal. Users don't care, but startups might get sued.

All of that aside, I agree that Grooveshark has built a great product. But I'd be kidding myself if I didn't also say the first song I searched for was Metallica and I got a massive list of songs I could listen to. I'm sure they wouldn't be happy.