WCF Web Service, Java Web Client, MustUnderstand headers not understood?

I'm hosting a WCF Web Service with the following WSDL (a simple service using wsHttpBinding and SSL for transport security):

<wsdl:definitions xmlns:wsdl="http://schemas.xmlsoap.org/wsdl/" xmlns:wsx="http://schemas.xmlsoap.org/ws/2004/09/mex" xmlns:wsa10="http://www.w3.org/2005/08/addressing" xmlns:tns="http://tempuri.org/" xmlns:soap12="http://schemas.xmlsoap.org/wsdl/soap12/" xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd" xmlns:wsp="http://schemas.xmlsoap.org/ws/2004/09/policy" xmlns:wsap="http://schemas.xmlsoap.org/ws/2004/08/addressing/policy" xmlns:msc="http://schemas.microsoft.com/ws/2005/12/wsdl/contract" xmlns:wsa="http://schemas.xmlsoap.org/ws/2004/08/addressing" xmlns:wsam="http://www.w3.org/2007/05/addressing/metadata" xmlns:wsaw="http://www.w3.org/2006/05/addressing/wsdl" xmlns:soap="http://schemas.xmlsoap.org/wsdl/soap/" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:soapenc="http://schemas.xmlsoap.org/soap/encoding/" name="MagicEightBallService" targetNamespace="http://tempuri.org/">
  <wsp:Policy wsu:Id="WSHttpBinding_TransportSecurity_IMagicEightBallService_policy">
    <wsp:ExactlyOne>
      <wsp:All>
        <sp:TransportBinding xmlns:sp="http://schemas.xmlsoap.org/ws/2005/07/securitypolicy">
          <wsp:Policy>
            <sp:TransportToken>
              <wsp:Policy>
                <sp:HttpsToken RequireClientCertificate="false"/>
              </wsp:Policy>
            </sp:TransportToken>
            <sp:AlgorithmSuite>
              <wsp:Policy>
                <sp:Basic256/>
              </wsp:Policy>
            </sp:AlgorithmSuite>
            <sp:Layout>
              <wsp:Policy>
                <sp:Strict/>
              </wsp:Policy>
            </sp:Layout>
          </wsp:Policy>
        </sp:TransportBinding>
        <wsaw:UsingAddressing/>
      </wsp:All>
    </wsp:ExactlyOne>
  </wsp:Policy>
  <wsdl:types>
    <xsd:schema targetNamespace="http://tempuri.org/Imports">
      <xsd:import schemaLocation="http://my.local.domain.name/MagicEightBall/MagicEightBallService.svc?xsd=xsd0" namespace="http://tempuri.org/"/>
      <xsd:import schemaLocation="http://my.local.domain.name/MagicEightBall/MagicEightBallService.svc?xsd=xsd1" namespace="http://schemas.microsoft.com/2003/10/Serialization/"/>
    </xsd:schema>
  </wsdl:types>
  <wsdl:message name="IMagicEightBallService_GetAdvice_InputMessage">
    <wsdl:part name="parameters" element="tns:GetAdvice"/>
  </wsdl:message>
  <wsdl:message name="IMagicEightBallService_GetAdvice_OutputMessage">
    <wsdl:part name="parameters" element="tns:GetAdviceResponse"/>
  </wsdl:message>
  <wsdl:portType name="IMagicEightBallService">
    <wsdl:operation name="GetAdvice">
      <wsdl:input wsaw:Action="http://tempuri.org/IMagicEightBallService/GetAdvice" message="tns:IMagicEightBallService_GetAdvice_InputMessage"/>
      <wsdl:output wsaw:Action="http://tempuri.org/IMagicEightBallService/GetAdviceResponse" message="tns:IMagicEightBallService_GetAdvice_OutputMessage"/>
    </wsdl:operation>
  </wsdl:portType>
  <wsdl:binding name="WSHttpBinding_TransportSecurity_IMagicEightBallService" type="tns:IMagicEightBallService">
    <wsp:PolicyReference URI="#WSHttpBinding_TransportSecurity_IMagicEightBallService_policy"/>
    <soap12:binding transport="http://schemas.xmlsoap.org/soap/http"/>
    <wsdl:operation name="GetAdvice">
      <soap12:operation soapAction="http://tempuri.org/IMagicEightBallService/GetAdvice" style="document"/>
      <wsdl:input>
        <soap12:body use="literal"/>
      </wsdl:input>
      <wsdl:output>
        <soap12:body use="literal"/>
      </wsdl:output>
    </wsdl:operation>
  </wsdl:binding>
  <wsdl:service name="MagicEightBallService">
    <wsdl:port name="WSHttpBinding_TransportSecurity_IMagicEightBallService" binding="tns:WSHttpBinding_TransportSecurity_IMagicEightBallService">
      <soap12:address location="https://localhost/MagicEightBall/MagicEightBallService.svc"/>
      <wsa10:EndpointReference>
        <wsa10:Address>
          https://localhost/MagicEightBall/MagicEightBallService.svc
        </wsa10:Address>
      </wsa10:EndpointReference>
    </wsdl:port>
  </wsdl:service>
</wsdl:definitions>

Why do I get errors when I try to consume this from Java? When I try to consume it using Axis2/Java, I get the error:

org.apache.axis2.AxisFault: Must Understand check failed for header http://www.w3.org/2005/08/addressing : Action

And when I try to use JAX-WS, I get the error:

javax.xml.ws.soap.SOAPFaultException: MustUnderstand headers:[{http://www.w3.org/2005/08/addressing}Action] are not understood

So far I haven't had any success with either of these, and I'm not sure whether a fix needs to be applied to the server or the client.

(See a related question I posted for more details, including the WCF Web.config).

Running:

ServiceClient sc = stub._getServiceClient();
sc.engageModule("addressing");

engages the Addressing module, fixing this issue.