I often find that using Google Search (the Video tab, with "site:youtube.com") allows me to find videos that don't show up in the YouTube search... or sometimes vice versa!