Update:
I got the right configuration with the following custom bindings.
The only problem is that the body does not get encrypted as expected, given the messageProtectionOrder="EncryptBeforeSign". It seems to be a bug of WCF.
<customBinding >
<binding name="gxWsSoapBinding">
<textMessageEncoding messageVersion="Soap12WSAddressing10" writeEncoding="utf-8" />
<security authenticationMode="MutualCertificate"
defaultAlgorithmSuite="Basic128"
messageProtectionOrder="EncryptBeforeSign"
securityHeaderLayout="Lax"
includeTimestamp="false"
messageSecurityVersion="WSSecurity10WSTrustFebruary2005WSSecureConversationFebruary2005WSSecurityPolicy11BasicSecurityProfile10">
</security>
<httpsTransport />
</binding>
</customBinding>
.......
<endpointBehaviors>
<behavior name="gxCustomBehaviorConfig">
<clientCredentials>
<!--Specify a certificate to use for authenticating the client SIGNATURE.-->
<clientCertificate findValue="privatekey.client" x509FindType="FindBySubjectName" storeLocation="LocalMachine" storeName="My" >
</clientCertificate>
<!--Cert used for encryption-->
<serviceCertificate >
<defaultCertificate storeLocation="LocalMachine" storeName="My" findValue="publickey.service.com" x509FindType="FindBySubjectName" />
<authentication certificateValidationMode="None" revocationMode="NoCheck"/>
</serviceCertificate>
</clientCredentials>
</behavior>
</endpointBehaviors>