Instantly determines the distance between the centroid of two U.S. ZIP codes (e.g. the straight line distance between two points).
And it even seems to be WSDL, which is apparently one of your requirements. (Would you not accept a RESTful web service?) But there's lots more on the first page of returned links. I suggest you do the same search and check out those sites for yourself.