Скорее не ответ, а в копилку обсуждения:
Не мог зайти в скайп у знакомых, они сами на это пожаловались. Через VPN, Tor - работало. Оставил так. Потом Tor стал отваливаться регулярно, спасало переключение выходных нод. Сейчас, действительно, не смог найти работающую.
Смотрел через Wireshark - все соединения просто отвергаются. Никаких firewall'ов, никаких ограничений у провайдера. Явно проблема на стороне серверов Skype. Это и с Tor и без него. Пробовал подбирать бесплатные прокси - всё ок, но они очень нестабильно работают.
Потом начал смотреть на эту тему в интернете. Оказалось, что после появления взломанного SkypeKit начались жесткие блокировки как IP, так и целых подсетей. Информация об этом была на хабре (в теме про ломаный SkypeKit и клиент). Т.е. достаточно кому то из вашей сети воспользоваться ломаным SkypeKit - и вы не сможете использовать Skype. С Tor'ами в этом смысле тоже все логично - пытались через него прокинуть соединения и все они попали под блокировку.
Написал в саппорт (не по Tor'ам, а чтобы с местного IP сняли блок). Мне ответили, что ничего они не блочат. Попросил уточнить, поскольку проблема явно на их стороне - ответили тем же. Пытался настаивать - все равно посылают к провайдеру или администратору сети.
Как то так. Проблема ясна, а что делать - не ясно. Знакомых прокинул через бесплатный VPN.
