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.
88115645-f61b-467a-8b66-6c0411609f65|0|.0
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>
8a5029d3-6c09-4b1c-a5b3-a4f5b213a3c8|0|.0