I had this error and all the configurations mentioned above were correct however I was still getting "The client and service bindings may be mismatched" error.
What resolved my error, was matching the messageEncoding attribute values in the following node of service and client config files. They were different in mine, service was Text and client Mtom. Changing service to Mtom to match client's, resolved the issue.
<configuration>
<system.serviceModel>
<bindings>
<basicHttpBinding>
<binding name="BasicHttpBinding_IMySevice" ... messageEncoding="Mtom">
...
</binding>
</basicHttpBinding>
</bindings>
</system.serviceModel>
</configuration>