Delete the "Skype" Entry in S4B Controlpanel - Federation and External Access - SIP Federated Providers. After that, run the following PowerShell cmdlet.
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 AlwaysVerifiable -Enabled $true -EnableSkypeIdRouting $true -EnableSkypeDirectorySearch $true
Close S4B Client and restart it afterwards. Have fun.