Sounds like you're going down the right lines. The correct order of deletes may be unresolvable without disabling/re-enabling constraints, especially if you have circular references spanning multiple tables (urgh).

You may have to test scripting and disabling the constraints, perform the deletes/moves, then re-enable/check constraints (making sure that they can re-enable without error, or rollback the whole transaction). Assuming everything does truly end up linking back to the parent key, the conflicts should resolve themselves when all the deletes have been processed.