I googled "zip code web service". The USPS might have one, but their server was too busy to respond. This one:
http://www.remotemethods.com/home/valueman/validati/zipcodes
has a web service whose description says
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.