Interoperability in a large-scale distributed system is challenged by by the diversity of node policies. We introduce AMPol (Adaptive Messaging Policy), a serviceoriented architecture that facilitates policy-aware, end-toend adaptive messaging between multiple parties. AMPol provides services for expressing non-functional QoS policies, finding them, and carrying out system extensions to adapt to them. We implement this approach with a web service middleware that allows parties to use policies for features like attachments, payment, encryption, and signatures. Our implementation demonstrates how AMPol can enhance the function of email messaging by enabling automatic deployment and use of features like cycle exhaustion puzzles, reverse Turing tests and identity based encryption without the need for global deployment or changes to the baseline messaging system.