Hi Akos ToTH 2,
If you use Skype for Business Edge Server, have you opened the port 4443 on firewall ?
The new Edge Server provides a new feature Skype Directory Search. Skype Directory Search functionality provides Skype for Business users with the ability to search for Skype contacts.

Also EnableSkypeIdRouting and EnableSkypeDirectorySearch attributes need to be set to true in the public provider settings (see later instructions) for Search to work.
New-CsPublicProvider -Identity Skype -ProxyFqdn federation.messenger.msn.com -IconUrl https://images.edge.messenger.live.com/Messenger_16x16.png
-NameDecorationRoutingDomain msn.com -NameDecorationExcludedDomainList "msn.com,outlook.com,live.com,hotmail.com" -VerificationLevel UseSourceVerification -Enabled $true -EnableSkypeIdRouting $true -EnableSkypeDirectorySearch $true
Best regards,
Eric