Greg Low has a nice suggestion imho.
Basically the idea is the following (from ADO.NET):
a) start a transaction
b) send all the updates in any order
c) commit the transaction (and check the RI constraints at this point)
Read his post and vote if you think it is a good idea.