Foros del web, para los que viven de bits

Tengo una red de varias Pcs (unas 250) distribuidas en tres edificios que se conectan entre si inalambricamente, y localmente cada edificio esta cableado. Resulta que ya hemos tenido el caso de tres pcs que pueden explorar perfectamente la red de microsoft (compartir archivos e impresiones en red) pero en ellas no se puede navegar en internet. Lo simpático es que esas mismas pcs que no se conectan a internet en un edificio, las llevamos a otro edificio y entonces si entran a internet.
Yo se que muchos pensaran "¿y por que no la cambia de edificio y listo?", pero me consume muchas horas hombre hacer los respaldos y reconfigurar usuarios... además quiero saber por que pasa esto...
Toda mi red esta configurada con direcciones ip privadas, tengo un enlace dedicado y dos servidores proxy en linux.
¿sera probelma de hardware? ¿spyware? ¿virus? (tenemos norton 2006 original y constantemente actualizado)...

Gracias y saludos