We used tools provided from mcaffee but we're still cleaning files and trying to track down all the culprits... This is really insane.

Are you using mcaffee as your main antivirus?

All the networks I've setup antivirus on use Symantec Enterprise, the users aren't given access to turn the client or the updates off.