I've found a case where the depgraph _complete_graph method pulls in an installed package to satisfy a dependency, when that installed package is already scheduled to be rebuilt in the current calculation via the @__auto_slot_operator_replace_installed__ set. This ultimately triggers a slot conflict which prevents the the correct solution from being found. I will post a patch that solves the problem, including a test case.
Patch sent for review: https://archives.gentoo.org/gentoo-portage-dev/message/2f00ddbd203cad82f3ac145c9be895ec https://github.com/gentoo/portage/pull/151
This is in the master branch: https://gitweb.gentoo.org/proj/portage.git/commit/?id=a83bb83909c5a6ac232c8eb5931b28027f4175af
Fixed in 2.3.6.