The above is the result of "Layout" -> "Tree" -> "Directed" with default settings except for "Orientation" set to "Left To Right" and "Orthogonal Edge Routing" enabled on tab "Directed".
Running the algorithm again after adding or removing nodes might indeed result in a new (placement) order within the columns. This cannot be helped - the result of layout algorithms does depend on the (insertion) order of the elements in the diagram.
However, a different placement order hardly qualifies as "completely messed up" - at least as long as your diagram is a tree. If you start inserting connections that violate the tree criterion, you are better of using "Layout" -> "Hierarchical" instead of "Layout" -> "Tree".