While I agree that the main problem is one of static typing tied to the schema, I believe this is what XML Schema was intended to do. I may be wrong — I did neither follow nor look up history here — but the whole point of XML Schema seems to be to move from DTDs to something that resembles a programming language’s type system. I also still maintain that even if it’s theoretically possible to use something other than XSD with WSDL, this doesn’t matter for all practical purposes (since I don’t believe that a critical mass of tool vendors is to support, say, RELAX NG anytime soon).
I know David Orchard’s versioning article, and it’s great and it shows how much he knows about XML Schema’s details and I’m going to use that information for my own Web services design work. Unfortunately, it also shows that all of the possible solutions differ only in the degree to which they suck. Versioning with XML should be, and I believe could be, trivially easy. Due to XML Schema, it clearly isn’t.