Has anyone dealt with this malware?

[LavCat]

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.