WCF offers very flexible approach of Input and Data Validation based on XML Schemas. The approach is flexible since the validation rules are expressed in form of XML schema and can be changed at any time without recompiling the solution.
I followed the steps detailed in How To: Perform Message Validation with Schema Validation in WCF and ended up with another working sample (imagine that!).
It took me a bit to struggle with the schema thing and then enabling debugging info on the service side (remember, WCF is secure by default) to understand what's going on and why it fails time after time.
In the end me and WCF made friends and I'd thought it'd be good to share with you the Visual Studio project. Download it here from my SkyDrive and save yourself some time.
My related posts