Skype for Business messaging skype user due to 'company policy'

We can successfully add regular Skype users to our Skype for Business contacts list but when we try to communicate with them we get the following message:  "This message wasn't sent to xxxx yyyy due...