Has anyone dealt with this malware?

[kandrathe]

Resetting the router to factory specs isn't really an option since it's a custom-configured corporate-class Netscreen as opposed to a Linksys you'd pick up at Staples. Neither one of the laptops we tried are "unprotected", although the corporate version of McAfee is probably as close to unprotected as you're going to get. Don't even get me started...

If it were malware in the network stack (something I wouldn't rule out), why do searches work fine on his home network?

Can you reflash the router with the image of the proper configuration? I kind of doubt that the problem is an infested router though. But someone may have changed a setting.

... and I would examine the netscreen logs to see "if" and "what" the router actually did to the packet, and then track back to the "why" of any rules or ip blacklisting. This is why I love a Linux laptop with a good packet sniffer (e.g. Wireshark). You can answer questions like... does it even get to the firewall, and does it get past it. How does it look different than a request from another computer that does work.