Here is how Persistence Order is determined for any SaveChanges request:

(1)                 Typically, a default Persistence Order is determined for all of the tables which participate in the save.  The default order is determined automatically by doing a “reverse topological sort”.  In rare cases, this may not be the order that you want, and if that is the case, you can override this Persistence Order with your own Persistencce Order,

(2)                 Deletions occur first on a table-by-table basis.  Deletions occur in reverse Persistence Order.

(3)                 Adds and updates follow next and at the same time on a table-by-table basis according to the Persistence Order.

(4)                 Within a given table and within a given SaveTable operation (Delete versus Add/Modify), there is no predictable order.

Some comments on your observations:

(1)                 Your comment that there is no predictable Persistence Order between child records and parent records is correct if child and parent records belong to the same table.

(2)                 The typical way to handle limitations of Persistence Order is to make multiple saves.  This is a problem if you want to do the save as a single transaction.  Here is a coment from our senior architect on the issue of setting dependencies among or ordering records of the same type when performing a save:

This is a hard problem.  We currently have no way of setting dependencies among or ordering records of the same type when performing a save.  What we actually do internally is a DataAdapter.Update() call for each individual table, and this method iterates through the data rows without regard to contents.  We don’t currently plan to change this logic, so let’s see if a workaround will be sufficient.