> Так подключаемся мы к облачному серверу линка, а не к локальному.
> В acl squid добавлены ip адреса lync серверов

Lync подключается по имени.
Посмотрите логи. access.log
Там будет написано, куда не пустило. А почему - смотрите конфиг.
Конфига общего нет. У каждого свой, свои правила.
И что у вас открыто - только вам знать.
Какие требования у провайдера услуг, предоставляющего облачный линк?
Указано, что нужен доступ на такие-то адреса, по таким-то портам ...
Может там порты не стандартные.

И еще повторюсь, что авторизацию могут запрашивать веб-сервисы Exchange. Наверняка почта у вас тоже в облаке и на Exchange.
Lync ищет запись autodiscover.имя.домена для подключения к сервисам.
А может и по имени https://имя.домена ...
В общем, посмотрите логи прокси, чтобы понять, к каким url-ам возникает запрос аутентификации, почитайте как работает autodiscover ...