Действительно, лучшим способом искать родственников в сети сейчас являются социальные сети. Нужно, правда, помнить, что даже самая редкая фамилия - не гарантия того, что все её носители являются родственниками, поэтому при поиске нужно обязательно учитывать место жительства собственных предков.
Хороший ресурс - форум сайта "Всероссийское генеалогическое древо": vgd.ru , существует много лет, там накопилось огромное количество информации о поиске родственников в разных регионах, есть много людей, которые уже исследовали те или иные фамилии.
Помимо ОБД "Мемориал" и Мемо.ру нужно обязательно вспомнить базу mil.ru, где собраны сведения о награждениях военными наградами до и после Великой отечественной войны. В отличие от "Мемориала" там указываются не только те, кто погиб, но и те, кто остался жив. Все три ресурса могут быть полезны для непосредственного поиска, когда знаешь имена-фамили-места проживания, так и для косвенного - когда нужно установить ареал распространения фамилии (в первую очередь, конечно, редкой - Ивановых-Кузнецовых много везде).
Интересная тема. Был опыт поиска родственников, дошел до городского архива и там слегка застопорился процесс
Если есть исходные сведения для поиска, то результативнее организовать поиск человека через адресный реестр. Возможности реестра таковы, что можно запрашивать выборку по неполным данным, а далее выбирать по региону проживания или даже по фото. Из минусов: только по РФ, сервис платный.