http://msdn.microsoft.com/en-us/library/system.runtime.serialization.datacontractserializer_members.aspx

So as it turns out, your XML stream must have the XML Nodes in Alphabetical Order when trying to deserialize XML data into an object.  Very wierd.

So as it turns out pretty much all the examples I have read online show no attributes when using the binaryMessageEncoder.

As it turns out, just like text encoding, you can add a readerQuotas element like this:

<binding name="MaintenanceServiceBindingConfiguration">
  <binaryMessageEncoding>
      <readerQuotas maxArrayLength="2147483647" maxStringContentLength="2147483647" />
  </binaryMessageEncoding>
  <httpTransport maxBufferPoolSize="2147483647" maxBufferSize="2147483647"
          maxReceivedMessageSize="2147483647" />
</binding>