О, я как раз на днях изучал этот вопрос и обратился в Поддержку. Вот, что мне ответили:
Все работает с помощью нашего API.
Вполне возможно, что у пользователя есть в телефонной книге Ваш номер, или наоборот. Тут существует множество различных алгоритмов, раскрыть которые мы не сможем, увы.
Вы можете отключить оповещения о возможных друзьях со своей стороны. Сделать это надо здесь, пункт "Возможные друзья" в разделе оповещений на почту. В настройках приложения для iPhone, пункт "Уведомления", надо отключить пункт "Друзья из контактов".
Возможность поиска друзей на сайте ВКонтакте с использованием записной книжки является одной из функций приложения ВКонтакте и не противоречит ни законодательству РФ, ни Правилам пользования сайтом ВКонтакте и Правилам защиты информации о Пользователях сайтаVK.com. В частности, в Правилах пользования сайтом ВКонтакте указано, что Администрация Сайта обрабатывает персональные данные Пользователя в целях предоставления Пользователю доступа к использованию функционала Сайта (см. п. 5.8.). В разделе 3 Правил защиты информации о Пользователях Сайта VK.com говорится, что Администрация Сайта осуществляет обработку информации о Пользователях, в том числе их персональных данных, в целях выполнения обязательств Администрации Сайта перед Пользователями в отношении использования Сайта и его сервисов.