According to the SOAP 1.1 specification this is required of HTTP clients.
6.1 SOAP HTTP Request
Although SOAP might be used in
combination with a variety of HTTP
request methods, this binding only
defines SOAP within HTTP POST requests
(see section 7 for how to use SOAP for
RPC and section 6.3 for how to use the
HTTP Extension Framework).
6.1.1 The SOAPAction HTTP Header Field
The SOAPAction HTTP request header
field can be used to indicate the
intent of the SOAP HTTP request. The
value is a URI identifying the intent.
SOAP places no restrictions on the
format or specificity of the URI or
that it is resolvable. An HTTP client
MUST use this header field when
issuing a SOAP HTTP Request.
Source http://www.w3.org/TR/2000/NOTE-SOAP-20000508/#_Toc478383528
From a quick Google it seems this is a common issue with Java and Axis, but there is some debate whether it is required. Could this help you convince the Java developers that they need to implement the header?
Edit:
The correct URI for your SoapAction
http header is defined in the WSDL document.
Goto http://mydomain.com/myservice.asmx?wsdl
Look for the wsdl:operation element for the method you are calling, it should have a child element soap:operation which has a attribute called soapaction, the URI in there is the one you should use. In a webservice i tested it looks like the namespace followed by / and the method name as follows.
<wsdl:operation name="AddTwoNumbers">
<soap:operation soapAction="http://mydomain.com/myservice/AddTwoNumbers" style="document"/>