OAK-850 and OAK-1584 we settled on an orderBefore() implementation that always recreates the child order list based on the names of the child nodes that are present in a parent. This is a somewhat expensive operation with lots of child nodes as seen in JCR-3793.
We could optimize the implementation further for the common case where the child order list is in sync with the actual list of child nodes. For example we could skip recreating the child order list when the name we're looking for is already included in that list. Over time this approach should still detect cases where the list becomes out of sync, and automatically repair the list when that happens.