It turns out that the change to RPC style was exactly what made the difference. Now the Java client can call into my .NET web service without a problem. Specifically, I added the following class attribute to my web service:
[System.Web.Services.Protocols.SoapRpcService]
This changed the format of the WSDL that .NET generates drastically. All the operations are still there, but instead of being in “message” format, they are in “RPC” format. I actually don’t know what that means, but it makes the clients work.
Now to make sure it doesn’t break our ColdFusion clients…