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>