Here is a rather unique approach to audio/video searching...
The SeeqPod search engine allows you to search and then play the results for both audio and video files it finds on the web.
It also has a PodCrawler tab where you can see other results it has found from other searches it has done, scrolling right on your screen. This could be a great way to discover new music you may never have heard of before.
You can add any item to your playlist, save playlists, share them, embed them on your site or blog, etc. (some options require you to sign up for a free account)
What I find interesting, and will probably be the thing to allow it to have a longer life and not be targeted by the **AA's, is that it will not allow you to actually download the files it finds....you can only play them in their player.