Maybe the reason the computers run windows is because some of the software they are using is something common, like a map program, which inevitably would have been written for windows. And if they aren't connected the the public internet, an antivirus program would have been unable to download its virus DB updates.
Still, this is coming off looking very very bad. They followed the how-to on the kapersky website? Seriously that was their best move? Now they can't figure out why it's coming back? Everyone involved in this has huge egg on their face. They are coming off as supremely incompetent.
Geez guys, pay me your government contractor rate to clean the place up. I'll run all the windows applications through wine or virtualbox in a linux environment, lock down network access with a fake proxy server, set up automatic daily software patches, and this will never happen again.