Forget Kazaa, it's installs too much crap on your computer (spyware, adware)
I found that using WinMX and Soulseek have been the best for searching for AMV, Anime, and Anime Music.
I have found that very few sites out there actually host media files (due to bandwith limitations and/or file size limitations) so using google or yahoo is fruitless unless you really like chasing down dead links or downloading files in parts.
www.winmx.com
www.soulseek.com
WinMX has been around a while (almost since the fall of Napster) so you'll probably have better luck finding files there (though you may wait a while before you can download). Soulseek is newer so there are not many users on it, but it has its advantages (like being able to download a whole folder of stuff with one click from a user).
Happy Anime Hunting
Kishikistsune
--thanks to winmx and soulseek and (sigh) yes, Kazaa, i have 2 cds worth of Final Fantasy AMV and Game Videos.