I have been experiencing a consistent issue attempting to upsert records to a custom model. The custom model uses an external id, which is the primary key from our mysql database. (MYID__c) The custom model contains records that point to one another. For example, there is a field within each record, 'Parent_ID__c' that can point to the MYID__c of another record within the model. (Parent-Child relationship)

After trying a number of different things (Serial vs Parallel Jobs, etc) I've narrowed the problem down to a child referencing a parent record within the same Batch. 

For example, I have 10 records in a batch. 5 are parent records, and 5 are children, such that each parent record has a single child. It doesn't matter whether it's a Serial Job or Parallel job, it always fails with an error like:

Foreign key external ID: 15102 not found for field MYID__c in entity My_Custom_Object__c, Salesforce statusCode: INVALID_FIELD

In the case of the 10 records the children for the first 3 parents always fail. That is the first three parent records provided to the Bulk API. (in this case XML is being used to send the records to the Bulk API)

If the entire 10-record set is upsert again the Bulk API successfully ingests all 10 records after 2-3 upsert attempts. (Each time there are errors on fewer records)

I've been able to upsert records for 8 other custom models with no issues. However this particular Custom Model is the only one that I have that has these parent-child relationships and that is getting this error.

Is this a known issue in the Bulk API and does anyone have any insight into any workarounds, if possible?