Como no has explicado como esta configurada tu red pues tengo que hacer suposiciones.
Si salen todas a traves de un proxy, es decir uno de los ordenadores sea el que tenga acceso a internet y todos salen por el. Si se cae el proxy te quedas sin internet claro, el proxy se puede caer por que este mal configurado, por que no pueda cone el trafico(tenga insuficiente memoria, poco micro), o si es un win98 o XP se te tostara seguro por que estos sistemas operativos no estan preparados para actuar como servidores, te recomiendo linux o su defecto un win2000 server. Es ta puede ser una razon, se te tuesta el proxy a la porra internet.
Si salis todos a traves de un router, el problema puede ser del router o esterno. Esterno no tienes nada que hacer solo hablar con tu proveedor, del router, pues puede que se te quede tostado, por que sea demasiado trafico para el(es un router malucho) o que este roto y se caliente y no funcione.
Ya te digo son suposiciones si no me dices como es tu red no puedo decirte mas.