A flush during a transaction can cause the org.hibernate.engine.spi.ActionQueue.InsertActionSorter#sort implementation to produce an incorrect ordering with subsequent constraint violation.
A simple test case is attached.
Looking forward to getting your new test case. We have several tests to check all associations, but the number of possible combinations is, indeed, large.
If you have a better solution, feel free to send us a Pull Request as well.
I've got a partial solution based on a depth first topological sort, but it doesn't pass all tests either, so needs some work...
But I'll finish the new test case first.
Fixed in 5.1 branch as well.