perl-cleaner slot conflict when upgrading perl (5.16 -> 5.18)

If you tried upgrading from stable amd64 to ~amd64 or otherwise done a big update of perl, you probably hit this weird perl-cleaner slot conflict:

# perl-cleaner --all
!!! Multiple package instances within a single package slot have been pulled
!!! into the dependency graph, resulting in a slot conflict:

dev-lang/perl:0

  (dev-lang/perl-5.18.2:0/5.18::gentoo, installed) pulled in by
    =dev-lang/perl-5.18* required by (virtual/perl-IO-1.280.0:0/0::gentoo, ebuild scheduled for merge)
    ^              ^^^^^                                                                                                                                  
    dev-lang/perl:0/5.18=[-build(-)] required by (perl-core/version-0.990.800:0/0::gentoo, installed)
                 ^^^^^^^^                                                                                                              
    (and 7 more with the same problems)

  (dev-lang/perl-5.16.3:0/5.16::gentoo, ebuild scheduled for merge) pulled in by
    =dev-lang/perl-5.16* required by (virtual/perl-Package-Constants-0.20.0-r3:0/0::gentoo, installed)
    ^              ^^^^^                                                                                                                                  
    (and 6 more with the same problem)

This is bug #506616, and the solution is to run the following command:

perl-cleaner --all -- --backtrack=30


If you're interested in some background, I first hit this with vim:

/usr/bin/perl -e 'unless ( $] >= 5.005 ) { for (qw(na defgv errgv)) { print "#define PL_$_ $_\n" }}' > auto/if_perl.c
/usr/bin/perl /usr/bin/xsubpp -prototypes -typemap \
    /usr/lib64/perl5/5.18.2/ExtUtils/typemap if_perl.xs >> auto/if_perl.c
Can't locate object method "new" via package "ExtUtils::ParseXS" at /usr/bin/xsubpp line 53.
Makefile:2455: recipe for target 'auto/if_perl.c' failed
make[1]: *** [auto/if_perl.c] Error 255
make[1]: *** Waiting for unfinished jobs....
make[1]: Leaving directory '/var/tmp/portage/app-editors/vim-7.4.193/work/vim74/src'
Makefile:26: recipe for target 'first' failed
make: *** [first] Error 2

This led to bug #486266 and running perl-cleaner.

Before I found the working solution I tried this:

perl-cleaner --reallyall

but it didn't help. Then I looked at dependencies of the package mentioned in the slot conflict error message:

virtual/perl-Package-Constants-0.20.0-r3: RDEPEND="|| (
    =dev-lang/perl-5.18*
    =dev-lang/perl-5.16*
    =dev-lang/perl-5.14*
    ~dev-lang/perl-5.12.4
    ~dev-lang/perl-5.12.3
    ~dev-lang/perl-5.12.2
    ~perl-core/${PN#perl-}-${PV}
)"

Both perl-5.16 and perl-5.18 satisfy the dependency, so I was surprised what's making portage unhappy. I also tried this (now not sure why):

perl-cleaner --all -- --newuse --keep-going

But the following packages were still failing:

app-editors/vim-7.4.193

app-accessibility/at-spi2-core-2.10.2

sys-auth/polkit-0.112-r2

Then I connected the dots: I can make perl-cleaner pass additional flags to emerge, dependencies seem to be correct (no obvious slot conflict), and the following message from emerge:

You may want to try a larger value of the --backtrack option,
such as --backtrack=30, in order to see if that will solve this conflict automatically. 

That led me to the final solution (perl-cleaner --all -- --backtrack=30) and bug #506616.