Interesting. I haven't even tried Facebook Graph search as I think it never even became available in my country. But I think the main difference is probably that in Facebook, it's generally not socially OK to contact strangers. In ICQ, you could set and communicate explicitly if you wanted to be contacted by strangers or not (and if not, you weren't searchable).