David Byrne is predicting a need for music search in a recent journal entry:

Soon enough a site will open that is like a Google search for music
downloads — downloads that are not copy-protected but you still pay for.
…
Consumers don’t care who they buy them from if the interface is easy
and intuitive. Soon enough iTunes consumers will find they have reached
the 5th authorized player on their tracks and the frustration will set
in when they can’t listen to the music they paid for. They’ll start to
look elsewhere.