WCF Authentication - An error occurred when verifying security for the message

You are specifying the client side to use BasicHttpSecurityMode.Transport whereas the service is expecting BasicHttpSecurityMode.TransportWithMessageCredential. This is a problem because the service is looking for the client credentials in the SOAP Message Header and the client will not send them with the binding configured this way.

Hence, this is why the username/password pair is not present in the Message Header as you are witnessing. So the event viewer was correct that there was a binding mismatch between the communicating parties.

Also set the ClientCredentialType on the client to BasicHttpMessageCredentialType.UserName for Message level security. By default BasicHttpBinding uses None which are anonymous clients.

Here's a code snippet describing the above changes:

var basicHttpBinding = new BasicHttpBinding(
                              BasicHttpSecurityMode.TransportWithMessageCredential);
basicHttpBinding.Security.Message.ClientCredentialType = 
                                     BasicHttpMessageCredentialType.UserName;

This can also be caused by the time being out of sync between client and server. If a certificate or signed token is invalid based off of time, the same An error occurred when verifying security for the message. message may be returned.