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>