Service Oriented Architecture approach in general and the Web services technology in particular play significant role in modern collaborative environments. However, it is not enough to have the business functionality of the partners packaged as (Web) services; there is also a need for business-aligned order of interaction between these services (business protocols). Furthermore, it is necessary to guarantee that these protocols are enacted in compliance with the effective policies and regulations. This paper discusses business protocol compliance issues and suggests some techniques for enhancement of business protocols for better compliance. Such enhancements, for example, can support the proposed structured proof of compliance concept and its construction mechanism, which together address the issues of both correct course of collaboration at its critical steps and existence of a tangible proof of correctness of the whole collaborative interaction. Such proof, consisting of individually signed and time-stamped evidence statements, can serve for various audit purposes and, if necessary, in the court of law.