It's clearly real that people search for social media information, but generally this is public information. The question explicitly states they're interested in how recruiters look at information that should apparently be private. Your link doesn't particularly prove that private searches are common:
Search only public content about the candidate on the Internet
I've heard certain reports that some companies ask for social media passwords, but A) I'm not sure how real/common that is B) If it's not outright illegal, it's a violation of Facebook's ToS C) if you give them your password, you know how they found your information, so it's not relevant here anyway.
So we're back at "real problems you face"; I don't really feel this question makes much sense without some reasoning behind it; did HR know something that should have been private on his facebook? Is it well known that they find this information (I still don't see evidence of this). The question started with "I am just curious" which is a huge red flag. I edited it out, but I don't feel the question has really risen above plain curiosity at this point. When you're "just curious" with your question, all too often you get answers that are "just guessing", and those don't really help anyone. At worst they they're incorrect to boot.
I disagree that "do they" is only appropriate for Skeptics; while it's certainly on topic for Skeptics if you found a notable claim of such behavior, it's still 100% on topic on The Workplace, and IMO much more relevant to workers than "how". I mean, how is "how" relevant if places don't do these seemingly impossible background checks? That takes the question out of practicality and into theory, which isn't really what the site is about.