Первое что приходит на ум контролировать самому.
Ну если идти дальше просто тестируйте с разными параметрами и логируйте ответ. Потом на оснвое их сравнивая с результатами ручного поиска видео выявляйте закономерность.
Кроме опцмций есть видео которыи удалены за нурушения авторских прав, есть видео с ютуба встроены, с других плеиров, старые видео[которые давно загрузили] вк(на флеше), и новые на хтмл5.
Если это все все равно не поможет грамотный мультакаунтинг чтоб не превышать количество запросов+ прокси по надобности.
Есть функции которые не предназначены для этого ну тоже могут помочь. Так же можно попробовать разные версии.
