What i usually do is just search for the artist or song title under the "All Types" and/or "Video" search and see what comes up. Though i don't usually spend much time looking for music videos.
I don't use the sub categories like "Music Video" much, unless I'm just looking around and not trying for something in particular. As you've seen, you get too many files that aren't related to what your searching for.
You may find some useful tips in this thread:
How to find music and video.