Solution found thanks to Johan Flikweert and Jibbe Oomes. It turns out that we received a wrong wsdl file.
The (xsd part of the) wsdl should contain:
<xsd:element name="document" type="xsd:base64Binary" xmime:expectedContentTypes="application/octet-stream"/>
Example:
<?xml version="1.0" encoding="UTF-8"?>
<xsd:schema targetNamespace="http://www.darwin-it.nl/MTOM" elementFormDefault="qualified" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns="http://www.darwin-it.nl/MTOM">
<xsd:element name="mtomRequest" type="MtomRequestType"/>
<xsd:complexType name="MtomRequestType">
<xsd:sequence>
<xsd:element name="document" type="xsd:base64Binary" xmime:expectedContentTypes="application/octet-stream"/>
</xsd:sequence>
</xsd:complexType>
<xsd:element name="mtomResponse" type="MtomResponseType"/>
<xsd:complexType name="MtomResponseType">
<xsd:sequence>
<xsd:element name="document" type="xsd:string"/>
</xsd:sequence>
</xsd:complexType>
</xsd:schema>
The outgoing XML (from Mendix) will then contain something like:
<ns1:document xmime:contentType="application/octet-stream" xmlns:xmime="http://www.w3.org/2005/05/xmlmime">
<xop:Include href="cid:78b05872-79a1-459a-a389-b42a7e5898a6" xmlns:xop="http://www.w3.org/2004/08/xop/include"/>
</ns1:document>
Note that the text xmime:contentType="application/octet-stream" xmlns:xmime="http://www.w3.org/2005/05/xmlmime"
is currently always included even if it's not specified in the wsdl (fix requested, ticket 374869, 463291, 463341).