I'm here in Redmond at the patterns and practices Summit, and yesterday Don Smith had some very interesting things to say about versioning of web services. He was polling the audience for opinions and scenarios, and I started to realize that I hadn't thought very hard about the problem. Typically in cases where I've wanted to version a web services, I've left the existing endpoint in place (supporting the old interface) and added a new endpoint which supports the new interface. I still think that's a pretty good solution. What I realized, though, was that there's no way to communicate the information about the new interface programmatically. It still pretty much requires a phone call.
Don suggested something like RSS (or actually RSS) to push information about new versions out to clients. Another suggestion was to have people actively "subscribe" to your service. That would not only handle the "push" notification, but you'd know how many people were actually using your old vs. new interface, etc.
I started thinking about something like a WS-VersioningPolicy. We already have standards like WS-SecurityPolicy, which carry metadata about how you should secure your use of a given service. Why not use a similar formal, programmatic method for distributing information about versioning policy. You could convey information like methods that are deprecated, where to find the new versioned endpoint (if that's your strategy), or define up front policies about how you will version your interface without switching to a new endpoint.
That still doesn't solve the "push" problem. Clients would have to not only consume the policy file at the time they start using the service, but presumably they'd have to check it from time to time. That suggests human intervention at some level. Hmmm.
This is a hard problem, but one that Don's pretty passionate about solving, so check out his blog for future developments in this space.