Клиент Skype при первом удачном подключении скачивает список IP-адресов супернод и в дальнейшем подключается к ним даже если не может разрешить имя домена в IP.

Заблокируйте категорию "Чаты и мессенджеры". Попробуйте удалить каталог Skype в папке AppData/Roaming каждого профиля пользователя на каждом компьютере и очистить кэш DNS командой ipconfig /flushdns.