WCF Message Security with Certificates error: Security token could not be validated

Question

I have a WCF service setup with Messager security using certificates. I am using self-signed certificates for the moment. I do not use the certificate store, but instead load my certificates on the fly.

The service works when I use MessageSecurity=None, but with security turned on, as soon as I make a call to a service endpoint, I get the error:

An unsecured or incorrectly secured fault was received from the other party. See the inner FaultException for the fault code and detail. --> At least one security token of the message could not be validated.

The relevant sections of my service configuration look like this:

<endpoint name="DB_msgAnonymousSecured" address="Secure" 
          binding="wsHttpBinding" bindingConfiguration="UploadServiceSecure"
          contract="DataStoreInterfaces.IDataStoreServices" >
</endpoint>

<wsHttpBinding>
    <binding name="UploadServiceSecure" >
        <security mode="Message">
            <!-- Message security with certificate authentication-->
            <message clientCredentialType="Certificate" 
                     negotiateServiceCredential="false" establishSecurityContext="false"/>
        </security>
    </binding>
</wsHttpBinding>

The certificates are configured in the code like this: Server:

using (WebServiceHost queryHost = new WebServiceHost(typeof(DataStoreServices.DatabaseServicesImplementation)))
                {
                    try
                    {
                        queryHost.Credentials.ServiceCertificate.Certificate = new System.Security.Cryptography.X509Certificates.X509Certificate2(Application.StartupPath + "\\Server.pfx");
                        queryHost.Credentials.ClientCertificate.Certificate = new System.Security.Cryptography.X509Certificates.X509Certificate2(Application.StartupPath + "\\Client.cer");
                        queryHost.Open();

                        while (true) //endless loop 
                        {
                            Thread.Sleep(100);
                        }

                    }
                    catch (Exception ex)
                    {

                    }
                }

Client:

var binding = new WSHttpBinding();
binding.Security.Mode = SecurityMode.Message;
binding.Security.Message.ClientCredentialType = MessageCredentialType.Certificate;
binding.Security.Message.EstablishSecurityContext = false;
binding.Security.Message.NegotiateServiceCredential = false;
EndpointAddress address = new EndpointAddress(new Uri(serviceEndpointAddress), EndpointIdentity.CreateDnsIdentity("CompanyXYZ Server")); //usually, the DnsIdentity is the domain name. In our case, it's the value that was entered during the creation of the self-signed certificate.

ChannelFactory<IDataStoreServices> cf = new ChannelFactory<IDataStoreServices>(binding, address);
cf.Credentials.ServiceCertificate.Authentication.CertificateValidationMode = X509CertificateValidationMode.None; //since our certificate is self-signed, we don't want it to be validated
cf.Credentials.ClientCertificate.Certificate = new System.Security.Cryptography.X509Certificates.X509Certificate2(Environment.CurrentDirectory + "\\Client.pfx");
cf.Credentials.ServiceCertificate.DefaultCertificate = new System.Security.Cryptography.X509Certificates.X509Certificate2(Environment.CurrentDirectory + "\\Server.cer");

IDataStoreServices channel = cf.CreateChannel();
response = channel.TestConnection(); //this line causes the exception

I have been struggling with this issue for weeks now and I am out of ideas. Does anybody have any hints for me why this isn't working?