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: https://archives.gentoo.org/gentoo-portage-dev/message/864ba15ba1df4edc134eef4dcb8d0f19 https://github.com/gentoo/portage/pull/70
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: https://gitweb.gentoo.org/proj/portage.git/commit/?id=d7af27b4166f9ce693203bfc92d9bf44d3db081c
Fixed in portage-2.3.3.
