The Server Side has a nice article about making service contracts more relaxed into convenants. Following this technique, services can be versioned by supporting multiple schemas for one service.
So we're basically talking about overloading service functions with different schema. I think this is a rather nice conceptual approach, although not directly usable according to the current Web Services. This is because the current WSDL schema does not support overloading of methods.
For example; the following code in .NET will yield a runtime exception:
[WebMethod]
public string HelloWorld(int input)
{ return "Hello World" + input; }
[WebMethod]
public string HelloWorld(string input)
{ return "Hello World" + input; }
The message given by ASP.NET is:
Both System.String HelloWorld(System.String) and System.String HelloWorld(Int32) use the message name 'HelloWorld'. Use the MessageName property of the WebMethod custom attribute to specify unique message names for the methods.
But, I still like the approach taken in this article to solve the versioning problem. The article can be found here.