WCF MessageContract complex type property not deserializing

Question

I have to implement a service to handle this SOAP message:

<soapenv:Envelope 
        xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" 
        xmlns:serv="http://www.company.com/Service">
    <soapenv:Body>
        <serv:ServiceOperation xmlns="http://www.company.com/Service">
            <serv:operationParam>X</serv:operationParam>
            <serv:operationHeader>
                <serv:headerParamA>12345</serv:headerParamA>
                <serv:headerParamB>ABCD</serv:headerParamB>
                ...

The message contract currently looks like:

[MessageContract(
    WrapperName = nameof(ServiceOperation),
    WrapperNamespace = ServiceNamespace,
    IsWrapped = true)]
public class ServiceOperation
{

    [MessageBodyMember(Name = "operationParam", Namespace = ServiceNamespace)]
    public string OperationParam { get; set; }

    [MessageBodyMember(Name = "operationHeader", Namespace = ServiceNamespace)]
    public OperationHeader OperationHeader { get; set; }

    ...

The string property operationParam is parsed correctly by my service. But whatever I do, I cannot get the "complex type" operationHeader to work.

With the code above, properties on the OperationHeader are always null, regardless of XmlType and XmlElement declarations:

[XmlType]
public class OperationHeader
{
    [XmlElement]
    public string HeaderParamA { get; set; }
}

I've tried variations of the OperationHeader class with no attributes, MessageBodyMember attributes, decorating the XML type as anonymous. Still null on all members of the OperationHeader class.

Something very strange is that if I do this instead:

    [MessageBodyMember(Name = "operationParam", Namespace = ServiceNamespace)]
    public string OperationParam { get; set; }

    [MessageBodyMember(Name = "operationHeader", Namespace = ServiceNamespace)]
    public XmlElement OperationHeader { get; set; }

Then the XML element parsed is not the operationHeader itself, but the first child element from the XML; headerParamA.

Does anyone know what my classes should look like?

I've tried to do it exactly as in this answer, but that only gives null for member properties on the complex type as well.

Or is the XML I'm sent broken somehow?