I have switched from “message” style to “RPC” style encoding of the WSDL in response to advice on the MSDN web site: http://msdn.microsoft.com/library/en-us/dnservice/html/service12052001.asp. Apparently Java uses RPC more frequently. Maybe it will make a difference.