incrediBILL - 5:24 am on Dec 28, 2012 (gmt 0)

If the visitors are accessing the site directly... ie, not through Google... that rules out that the warning screen is due to cloaked malware (of the sort that would be visible only to Googlebot or to visitors coming in through Google).

That's not true because the browsers, like Firefox and Chrome, use the Google Safe Browsing API https://developers.google.com/safe-browsing/ and the website will pop an error when using those browsers no matter how you try to access it until it's removed from that list.