Do you recognize this situation?
Your web service is correctly configured. SPN’s have been set, delegation is covered, you can read the WSDL from a computer in the domain. But access to the web service is denied as soon as you connect from a computer outside of the domain.