Прокси - это уже существенный шаг в направлении обеспечения безопасности локалки.

Существенно сузить "сектор обстрела" извне поможет официально узаконенная вами на предприятии "фашистская" фильтрация трафика на прокси-сервере. Лучше всего по белым спискам, но в крайнем случае хотя-бы по чёрным. При условии, что мимо прокси никто из локалки в инет не ходит, в т.ч. и с самой машины с прокси-сервером. Тогда проникновение извне или утечка наружу станут возможными лишь с веб-трафиком и загружаемыми извне файлами (эксплойты, трояны и т.п.) А этот риск тоже можно существенно минимизировать антивирусным ПО.

Также не забываем о необходимости наличия службы обновления вендов и прикладного ПО по всей локалке. Ну и о каком-нибудь централизованно управляемом антивирусе. Дыры в софте латать и а/в базы обновлять надо всегда, везде и чем побыстрее.

Ну и на шлюзе, естественно, никаких listen ports наружу, и внешний IP-адрес желательно динамический. Если всё-таки наружу что-то должно смотреть, например ssh - обновить его до последних версий, настроить в нём авторизацию по ключам и ограничить количество попыток соединения в единицу времени, при этом на левый порт его выносить уже не обязательно. Также желательно максимально ограничить перечень адресов, с которых возможен доступ по ssh и прочим протоколам на/через шлюз. Далее остаётся только бдеть за сохранностью закрытых ключей. В этом существенно помогает указание паролей при генерации ключей. Как вы уже поняли, ОС на шлюзе очень подразумевается НЕ виндовс

Ещё можно, конечно, извратиться и пускать в инет, например, только особым образом настроенные виртуальные машины и прочие песочницы. Но на любом предприятии обязательно найдутся умельцы, которые захотят, найдут время и смогут пробросить доступный им инет на свою основную машину. Да и от хождения файлов с инета по локалке одно это никак не спасёт.

Средства обеспечения безопасности внутри самой локалки - это уже другой обширный вопрос.

Ну если у вас уже столько компьютеров, то неплохо бы задуматься уже и об IPS.
К примеру IBM Proventia IPS GX-series (в режиме inline-protection)
Полезно, когда на прокси-сервере антивирусный модуль прикручен.
И "+100500" - фильтрация, ограничения, политика.

По поводу переустановки систем - образы сделайте Акронисом.

Shanker, а кто мешает (кроме лени конечно   ) присоеденить все машины в офисе к NT домейну, выделить их в разные OU по виду деятельности и ограничить через GPO по мере их "веса" в компании. Обновления винды опять же через GPO в нужное время. IPSec  трафик внутри LAN для защиты от ARP poisonning. И никуда, никто, никогда не вылезет с любыми привилегиями(кроме domain admin) из тех рамок, куда вы их загоните. На интернет гейтвее: спам защита и корпоротивный антивирус. Для кого все это делалось (все эти инструменты и технологии) если ими не пользоваться?!