If you have an association like this: Part 1 <|-- 0 Car, then each Part has a reference to at most one (!) Car. So if you have a Part called 'Engine' which has a reference to a Car called 'Audi', and later you set the reference on 'Engine' to a Car called 'Ford', then the reference to 'Audi' is overwritten. Apparently, in your project each Part can refer to multiple Cars, and each Car can refer to multiple Parts, so you should use a reference set instead of a reference.
With some outside help I've now fixed it with a custom microflow for saving my XML mapping, it does the following:
The XML Mapping sends the Car object and Part name to my microflow. There I retrieve the Part from the database with the follow constraints:
[Car_retail.Part_Car = $XMLMappingParameter]
[Name = $Name]
First it checks if the associated Car object matches the one the XML Mapping gives. Then it checks that the Part name matches the Name I get from the XML mapping.
If this returns something, it sends the ExistingPart through. If not it creates a new Part object and sends that.