Even though it probably is unsupported I found a way to get what I want:
/api/data/v9.0/contacts?fetchXml=<fetch version="1.0" output-format="xml-platform" returntotalrecordcount="true" page="1" count="2147483646" no-lock="false">
<entity name="contact" >
<attribute name="statecode" />
<attribute name="entityimage_url" />
<attribute name="fullname" />
<order attribute="fullname" descending="false" />
<attribute name="parentcustomerid" />
<attribute name="emailaddress1" />
<attribute name="company" />
<attribute name="contactid" />
<link-entity name="msdyncrm_segment" from="msdyncrm_segmentid" to="msdyncrm_segmentmemberid" alias="bb" >
<filter type="and" >
<condition attribute="msdyncrm_segmentid" operator="eq" uitype="msdyncrm_segment" value="[GUID of segment]" />
</filter>
</link-entity>
</entity>
</fetch>
There is a plugin on the contacts entity delivered by the marketing solution that fires on "RetrieveMultiple". There seems to be some ugly programming inside, which retrieves the query from the segment and transforms it into a query against the D365 data. It also handles paging, which probably is implemented for the subgrid view inside the members section of the segment form. 2147483646 is the max amount of records you can retrieve for 1 page. When using the max int value (2147483647) no records are returned. All above results in an error.