When trying to communicate with external Skype people our Skype for Business Office 365 users were getting the message “This message wasn’t sent to … due to company policy”
When we tried to add an external contact we would get the message “..or it is outside your organization and is not federated with your company..”
My External Sharing rules for Skype in the admin center under Settings => Services & add-ins => Skype for Business were set to allow external sharing.
The clue was in the message “not federated with your company”. I went back to basics and used the “Check DNS” option under Setup => Domains to verify configuration on the DNS for the effected domain.
I found there was issues with the service locator SRV records for Skype.
Skype requires two SRV records on the name server for the domain and without them external communication will not work as expected.
For my SRV records the target was correct but my domain name was appended to the the end of the target. The strange thing was when I looked at the configuration on the name server for this domain the settings seemed fine. For this domain my name server was daily.co.uk
In the end it turned out I was missing a period (.) at the end of the targets. Daily.co.uk and maybe some others will append the domain name to the end if you don’t add a period after the .com making the values invalid and Skype external communications fail.