Inserts are indeed grouped per type, as the batch system requires that, however that's not going to cause FK issues. The thing is that the sorting of the elements groups the elements as well in one go otherwise we have to go over the graph multiple times. The sorting is done in such a way that the dependent is always inserted prior to the depending entity.
We did have a bug in the code however where not all entities were inserted in some cases, i.e. when you had multiple graphs in the unit of work. This bug was fixed on December 28th 2018. If you used a hotfix build of 5.5.1 uploaded prior to that date, you ran into this issue. If you used a build released after that, then it's unrelated to this.
However I suspect the issue you ran into is this issue. There's no way the PK side is inserted after a depending FK side, the graph sorter takes care of that. (Using a topological sort of the graph at hand. This code isn't different from earlier versions)
The grouping code does the following:
// now we have to sort the insert queue based on the sorted types list, so all entities belonging to a given type have to be placed in the slot of the type.
// meaning, if we have as sorted types: Customer, Employee, Order, and as entities in the insert queue: Customer1, Order1, Customer2, Order2, Employee1, Order3,
// the insert queue will become: Customer1, Customer2, Employee1, Order1, Order2, Order3.
// we can skip this step if there's just 1 type or we're processing updates as we'll leave those alone.
so it abuses the fact that a PK side can always moved to the a spot earlier in the queue as long as it never ends up after an entity of a type that depends on an entity of the type it is of. So a Customer can't end up being inserted after an Order as the type 'Order' depends on the type 'Customer'.
It was this code which botched multiple graphs in a single unit of work (as in: it removed parts of the queue and therefore not all entities were inserted, leading to FK issues). Looking at your description, it's what you had: multiple parent/child mini graphs which weren't connected.
The RTM release of 5.5.1 is scheduled for today, so we'll proceed with that. If you have the same recurring problem after the RTM release of 5.5.1, please post back in this thread asap so we can fix it for you (pending a repro case of course ) as soon as possible so you can utilize 5.5's new features