You only got found if you explicitly marked yourself as available for a chat, which was an opt-in choice that could be easily toggled on and off, or left off all the time if you just wanted to use ICQ to chat with your friends as current IMs are used. And you could omit information, e.g. you could fill in your hobbies but not gender if you didn't want to be found by gender. And the privacy settings were much more understandable and transparent than in e.g. Facebook.
I guess there would be creeps, as anywhere where you can be exposed to unknown people, but I don't think the problem was worse than elsewhere. In fact, in my later experiences in chats, dating sites, etc., most women seemed to be (understandably) on the defensive due to the amount of stalkers and creeps they had to endure regularly, and in ICQ it didn't seem so much that way, I got plenty of conversations, girls (and guys) giving me their address for exchanging stamps or letters, etc., which I found much harder later in other media. Although maybe it's that both the Internet and myself were young and naive back then.
Anyway, if stalkers did become a big problem, surely the tech could have improved to deal with it.
There are probably several factors, but I think the main reason it was abandoned is simply network effects. MSN Messenger rose for reasons orthogonal to this, and then no one of the main IMs that succeeded it implemented this. Sadly, the question of what IMs gain more traction depends more on network effects than actual quality (see Whatsapp vs. Telegram, etc.)