Обнаружил, что есть простой, быстрый, дешевый и главное — легальный способ проверить, есть ли страница в поисковом индексе гугла. Запрос вида inurl:<требуемый адрес> в Custom Search JSON API вернет 0, если страницы нет в индексе и >0, если она там есть.

100 запросов в день бесплатно, дальше 5$ за каждую тысячу запросов. Красота!

P.S. У желающих создать свой сервис по поиску в интернете на основе этого API — мало что выйдет, для доступа к JSON API нужно указать не более 10 доменов, по которым будет ограничен поиск.