WCF and "Error in deserializing body of reply message for operation …" errors

These days I had to update a component that is used in Microsoft Dynamic AX. I don’t know to work with AX, but some time ago I had to write a component in C# that calls a WCF service of a 3rd party and is used by an AX application.
The client proxy from C# component was update with the new client proxy; the code was also updated with the new logic. The unit-tests were updated also and we had a full green. Perfect, we send the component to AX team to update the reference to the component.
They come back to us with a big ugly error:

Error in deserializing body of reply message for operation …

WTF, we had the same endpoint. We had a client proxy that works on our unit-tests and a command line test application, but when AX make calls using our component we get this great error message. The oddest thing is that we receive this error even if the message that is returned from the endpoint has only 20 characters. Before updating the AX worked great with our component.
Looking over the internet we found we should need to increase the message size. We increased the size of the message like this:

<readerQuotas maxDepth="999990" maxStringContentLength="999990" maxArrayLength="999990" 
maxBytesPerRead="999990" maxNameTableCharCount="999990" />

This can be updated from code, if you have a custom binding that is set from code:

bindingElement.ReaderQuotas.MaxArrayLength = Int32.MaxValue;
bindingElement.ReaderQuotas.MaxBytesPerRead = Int32.MaxValue;
bindingElement.ReaderQuotas.MaxDepth = Int32.MaxValue;
bindingElement.ReaderQuotas.MaxNameTableCharCount = Int32.MaxValue;
bindingElement.ReaderQuotas.MaxStringContentLength = Int32.MaxValue;

Get what? The problem was solved, everything works as expected. The interesting thing is that even if the message from the servers was very small we still received the error message if we don’t set the reader quotas.
The error was pretty interesting, because we received this even if the message was extremely small.