region-order was removed because at that time it was not clear how to compute the region dimensions for the auto cases. Since the current model offers a solution (that plays nicely with a possible region order), we should bring the region-order back. Doing so will lift the constraint that comes with strict document order.
I'd want to see a use-case first.
The use case could be laying out regions in a table where the intended region order goes from top left to bottom left and back up to top right. The cell order would not allow this, but you could use region order.
Added to the list of features to consider for level 4: http://wiki.csswg.org/spec/css-regions-4