С другими компьютерами, это не в этом же офисе? В скайпе файлы передаются не через сервера скайпа, а напрямую. Поэтому нельзя сунуть их в оффлайн.
Кстати, неделю назад где-то и обновление скайпа было, если не путаю ничего. Может быть и поменяли, что теперь через сервер, причем, с подключением снаружи.
На компах какая-то гадость, вроде стенок, есть? Антивирусы? В одной подсети, полагаю? Посмотри netstat в момент подключения, снифером, куда лезет.