Actually, I think the problem was misreported. It seemed as though google flagged its own interstitial page as malware, as all the search result links showed as http://google.com/search?interstitial=<URL>, and THAT page was malware -- unless I'm overlooking something obvious, like the interstitial page is only shown when adware is detected.

Regardless, the search engine worked perfectly, it was just the links that weren't working. Simply removing the 'google' part of the URL allowed me to get to the sites just fine.