http://www.google.com/support/forum/p/W ... 94db&hl=en
The problem is not with Google ... it is with the criminals that create and distribute malware ... and the problem now resides on your own computer. I don't say this to be uncompassionate ... but to educate. The responsibility is on the computer owners to be aware that it takes more than an anti-virus product to keep your system "safe." If you are not able to resolve the problem with multiple products, you might consider visiting a malware removal forum where they can provide assistance with more advanced tools.
There is not a single product that is guaranteed to be able to identify and resolve every single case of malware infection that exists. Each version can change many times a day. While your particular experience may be limited to Google searches, t is quite possible for the same type of behavior to affect your use of other search engines as well. That all depends on the malware author's intent.