Links to root domain from search engines don't work, but direct links and links from other referrers do

I've got a really odd situation with a wordpress website I manage - when I directly type the domain into my browser, the site comes up just fine - similarly, when I click a link to my site from another website (like LinkedIn, as one example), the site comes up just fine. Here's the working example:

However, when I search for my company on major search engines (Google and Bing both, but there may be others), the link appears to go to my domain and clicking it shows my domain in the browser bar, but I instead get a (broken) ad page:

(Bing also sees the title of my website as "Buy Generic Cialis - Get Bonus Pills", though Google still has my original/correct title). This happens everywhere I've tested it, so it's something server-side and not a client issue (and I can replicate working and broken on the same client). Somebody mentioned a PHP vulnerability (my host was using 5.4 and I've since upgraded to 5.6, but it's still happening), but if my site was compromised, do I have to redeploy Wordpress to correct it or is there another obvious solution?

I don't want to post the domain directly because they owner is (rightfully) a bit embarrassed about the potential confusion, but if you message me, I'll share it so you can see for yourself.