This problem is triggered when a slot operator dependency becomes broken due to a sub-slot change in a dependency, and the rebuild fails (or the rebuild is not triggered due to --complete-graph-if-new-ver being disabled). After the dependency is broken, in later dependency calculations, emerge does not trigger a rebuild in order to resolve it.
This test case demonstrates the problem: http://git.overlays.gentoo.org/gitweb/?p=proj/portage.git;a=commit;h=9fead7ac9b4d819bdbe4321c78e325dced7c51a8
This is fixed by these two commits: http://git.overlays.gentoo.org/gitweb/?p=proj/portage.git;a=commit;h=57604eaf869b544aac9e8ed2e270dcc6be3cf739 http://git.overlays.gentoo.org/gitweb/?p=proj/portage.git;a=commit;h=cbe52a133e4480cefd22ca51dd0c133c09eb93f4
This is fixed in 2.1.11.31 and 2.2.0_alpha142.