Graph search still works surprisingly well if you know what you can search for.

Try http://graph.tips/

Graph Search always surfaced relevant information that explained why they matched a search. For example “Friends who visited London” might say “Checked in at Tower Bridge” below a result.

You’re right that people didn’t understand Facebook’s privacy model. People assume that privacy by obscurity is a guarantee. Never mind that anyone could write a bot that did what Graph Search did. Graph Search was actually more conservative than it needed to be to avoid surprises.

In the end that all mattered less than the fact that it wasn’t solving a problem people had.

FG probably would allow advertisers to bypass FB products for identification of potential customers and hence is not in best financial interest of FB.

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).

I remember when Facebook hyped the Graph search as the next big thing, a truly social search engine. Years later I only occasionally remember about its existence when trying to find someone/something specific on Facebook, and even then it's at most mildly helpful.