Важно, чтобы сайт, по которому осуществляется поиск, был подтвержден в вебмастере под тем же аккаунтом, под каким создается поиск. Это и есть подтверждение прав на сайт.

У вас так такая ситуация, и все равно есть сообщение о том, что  "URL, не подтверждённые в Яндекс.Вебмастере" ?