Error in WCF client consuming Axis 2 web service with WS-Security UsernameToken PasswordDigest authentication scheme

I can confirm that the UPDATE from my question actually works:

object IClientMessageInspector.BeforeSendRequest(ref System.ServiceModel.Channels.Message request, System.ServiceModel.IClientChannel channel)
{
    UsernameToken ut = new UsernameToken("USERNAME", "PASSWORD", PasswordOption.SendHashed);

    XmlElement securityElement = ut.GetXml(new XmlDocument());

    MessageHeader myHeader = MessageHeader.CreateHeader("Security", "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd", securityElement, false);
    request.Headers.Add(myHeader);

    return Convert.DBNull;
}

And the client:

CustomBehavior behavior = new CustomBehavior("USERNAME", "PASSWORD");
client.Endpoint.Behaviors.Add(behavior);

The error message was unrelated. The security header works with a very simple basicHttpBinding:

<basicHttpBinding>
  <binding name="BasicSOAPBinding">
      <security mode="Transport" />
  </binding>
</basicHttpBinding>

This question is well written -- many thanks. In reference to @Junto's "How do I use this" comment, it turns out that the SecurityHeader param on the service method can be used to add the header. I've included an example below. I believe that what's happening is that the SvcUtil.exe tool is barfing when trying to read the WS* DTDs. This is not obvious when you use the "Add Service Reference" wizard. But it is very obvious when you run svcutil.exe from the command line. Because svcutil.exe fails to read the WS* DTD's, the SecurityHeader object is not well developed. But Microsoft gives you an out with the .Any property. You can serialize the UsernameToken class right into the .Any property and your header will be added to the message. Again, thanks for this excellent question.

How to use the SecurityHeader parameter to add a UsernameToken security header:

Required tools:

Fiddler2 (or similar) -- you really can't figure any of this out without inspecting the http headers.

Required Reference:

Microsoft.Web.Services3.dll -- you can reference this 2.0 framework assembly from your 4.0 assembly

WCF service call:

// Initialization of the service...
_service = new MyService("MyEndpoint", RemoteUri);

// etc.    

// Calling the service -- note call to GetSecurityHeader()
_service.ServiceAction(GetSecurityHeader(), "myParam1");

// etc.

/// <summary>
/// Construct the WSE 3.0 Security Header
/// </summary>
private SecurityHeader GetSecurityHeader()
{
    SecurityHeader h = new SecurityHeader();
    UsernameToken t = new UsernameToken(RemoteLogin, RemotePassword, PasswordOption.SendPlainText);
    h.Any = new XmlElement[1];
    h.Any[0] = t.GetXml(new XmlDocument());
    return h;
}

App.config:

  <system.serviceModel>
    <bindings>
      <basicHttpBinding>
        <binding name="MyBinding" closeTimeout="00:01:00" openTimeout="00:01:00"
            receiveTimeout="00:10:00" sendTimeout="00:10:00" allowCookies="false"
            bypassProxyOnLocal="false" hostNameComparisonMode="StrongWildcard"
            maxBufferSize="1048576" maxBufferPoolSize="524288" maxReceivedMessageSize="1048576"
            messageEncoding="Text" textEncoding="utf-8" transferMode="Buffered"
            useDefaultWebProxy="true">
          <readerQuotas maxDepth="32" maxStringContentLength="8192" maxArrayLength="16384"
              maxBytesPerRead="4096" maxNameTableCharCount="16384" />
          <security mode="Transport">
            <transport clientCredentialType="None" proxyCredentialType="None"
                realm="" />
            <message clientCredentialType="UserName" algorithmSuite="Default" />
          </security>
        </binding>
      </basicHttpBinding>
    </bindings>
    <client>
      <endpoint address="http://myservice.com/service.asmx"
          binding="basicHttpBinding" bindingConfiguration="MyBinding"              contract="MyContract"
          name="MyEndpoint" />
    </client>
  </system.serviceModel>