Bug 597752, comment #7 highlights some logic which can lead to incorrect re-ordering of choices in the dep_zapdeps function. The highest_cpv variable is used to keep track of the highest version of a given $CATEGORY/$PN that is matched by the atoms in the current choice. This variable currently does not account for cases where the highest match does not satisfy all atoms for the $CATEGORY/$PN, which can lead do incorrect re-ordering of choices as discussed in bug 597752, comment #7. What is needed is something like the depgraph._minimize_children method, which selects the minimum number of packages that satisfy all of the atoms for a particular choice.
I've posted a patch for review:
Note that package selection consistency provided by depgraph's _dep_check_composite_db only takes affect after a package is added to the graph. Therefore, for packages that have not been added to the graph yet, dep_zapdeps needs to handle package selection consistency internally.
This is in the master branch:
Fixed in portage-2.3.3.