See here for general tips & info:
http://www.gnutellaforums.com/showth...threadid=51850

Try using 'all types' to search, rather than 'video'. It can give better results.
Type in something like artist name - avi (or whatever format you're looking for). Or artist - genre - format eg Joe Bloggs hip-hop avi