Connections from my Win2k PC to the net were OK part of the time, but slow. Windows file sharing was glacial to or from the box. Printing to a local Lexmark TCP/IP printer would fail.
But it was only my office. A D-Link DSS-5+ 10/100 switch on my desk was apparently crapping out. I replaced it with a Netgear FS105 and the problems went away.
Are the users on the same subnet sharing a router or switch somewhere? Have you tried a different DNS? [link|http://z.iwethey.org/forums/render/content/show?contentid=202375|Greg's ] seem to work pretty well.
I don't know of any virus/spyware that would cause those symptoms, but I haven't kept up with such things as much as I probably should.
HTH. Luck!
Cheers,
Scott.