Web services technology is prevailing for business-to- business integration due to its well defined infrastructure enabling interoperability among heterogeneous applications. However, this interoperability promise also poses a difficulty in building a Web service management framework which can work across organizational boundaries. In this paper, we argue that existing Web service management systems are inflexible in the way they handle QoS violations of a composite service.We suggest to use an intermediate step, called QoS conflict mediation, to make existing Web service management systems more flexible. Our mediation approach is based on a combination of two new ideas. Firstly, we propose to use techniques from the AI field of Distributed Constraint Satisfaction to intelligently mediate any QoS conflicts between services in compositions involving multiple service providers. Secondly, we propose a novel monitoring system, based on cryptography, to verify the conformance of service providers to the specification of a selected DisCSP algorithm - the Asysnchronous Aggregate Search (AAS). This enables our DisCSP based QoS mediation to be used in the real Web services environment where full collaboration between providers may not always be guaranteed.