After spending hours on looking at options on internet and solution provided by Pedro Felix here I have cracked it using a new feature available in .net 4.0 and 3.5 SP1. Pedro's solution is great but it was deviced when 3.5 SP1 was not available to hand and therefore not the best option today.
Problem: Many organisations use hardware accelerated NLB for SSL encryption and decryption. This alleviates SSL processing load from actual web servers and also makes it easier to update the SSL certificate as there is only place to update the certificate. The problem is if you want to use Username/Password as a credential over secure transport (SSL) you need to chose security mode as "TranspoprtWithMessageCredential" in binding (WSHttpBinding). As soon as you do this WCF will ensure message received in IIS is encrypted with SSL. Now as SSL encryption/decryption is performed by NLB here WCF throws the error.
Solution: .Net 3.5 SP1 and 4.0 comes with a new properties allowInsecureTransport and enableUnsecuredResponse on SecurityBindingElement. Setting these properties to True allows WCF to ignore the strict rule of checking if message is SSL encrypted. This property is however not exposed by built in WSHttpBinding. To make use of it you will need to create a custom binding which set these properties correctly and also allow username/password in SOAP header using standard WS security protocols. Following custom binding works like "TranspoprtWithMessageCredential" mode but without HTTPS.
Server binding and endpoint config-
<bindings>
<customBinding>
<binding name="customHttpBinding">
<security authenticationMode="UserNameOverTransport" allowInsecureTransport="true" enableUnsecuredResponse="true" />
<httpTransport/>
</binding>
</customBinding>
</bindings>
<endpoint address="" binding="customBinding" bindingConfiguration="customHttpBinding" name="processMessage" bindingName="customHttpBinding" contract="SecurityCheckService.IService1"
Client binding and endpoint config-
<bindings>
<customBinding>
<binding name="customHttpBinding">
<security authenticationMode="UserNameOverTransport" allowInsecureTransport="true" enableUnsecuredResponse="true"/>
<httpTransport/>
</binding>
</customBinding>
</bindings>
<
client>
<endpoint address=http://NLB_IP_OR_DNS/SecurityCheckService/Service1.svc binding="customBinding" bindingConfiguration="customHttpBinding" contract="ServiceReference1.IService1" name="processMessage" behaviorConfiguration="via"/>
</client>
<
behaviors>
<endpointBehaviors>
<behavior name="via">
<clientVia viaUri="https://NLB_IP_OR_DNS/SecurityCheckService/Service1.svc"/>
</behavior>
</endpointBehaviors>
</behaviors>
Note ClientVia behavior. This is required as service on IIS does not know about SSL. SSL is stripped off by NLB. This client config will ensure that the request is sent to Https address but "To" Soap Header block contains Http based address so that you do not get Address Filter mismatch error.
I use custom authenticator/validator to validate the credentials coming into the SOAP header. Idea is to store credentials in SSO and validate them against the hash of the password. It's easy to create a custom validator which is explained here