Ну для начала неплохо бы проверить как работает DNS.
upd ----------------------------------------------------------------------
Поскольку проблема вызвана вирусами, то сказать что конкретно повреждено трудно.
Попробуйте на одном из проблемных компьютеров выполнить следующие команды и посмотрите результат
ipconfig /flushdns
nbtstat -R
nbtstat -RR
netsh int reset all
netsh int ip reset
netsh winsock reset
netsh interface tcp set global autotuninglevel=disabled
И еще один момент - чтобы более точно локализовать проблему попробуйте пинговать известные ресурсы в интернете по IP адресу - пойдет ли пинг. Ну или попробуйте скажем запустить тимвьювер или скайп - увидят ли они доступ в интернет, или нет. Уже будет ясно в какую сторону копать.