If you try to replace an old-style virtual with new provider, it doesn't resolve virtual blocks because dependencies remain bound to the old provider. For example, when trying to replace mail-mta/exim with mail-mta/ssmtp: Calculating dependencies... done! [ebuild N ] mail-mta/ssmtp-2.62-r8 USE="ipv6 ssl -maxsysuid -md5sum" 56 kB [blocks B ] mail-mta/exim ("virtual/mta" is blocking mail-mta/exim-4.72, mail-mta/ssmtp-2.62-r8) Total: 1 package (1 new), Size of downloads: 56 kB Conflict: 1 block (1 unsatisfied) * Error: The above package list contains packages which cannot be * installed at the same time on the same system. (mail-mta/exim-4.72, installed) pulled in by mail-mta/exim required by (app-crypt/gnupg-2.0.16-r1, installed) mail-mta/exim required by (sys-process/vixie-cron-4.1-r11, installed) mail-mta/exim required by (dev-lang/php-5.3.3-r1, installed) (and 2 more) (mail-mta/ssmtp-2.62-r8, ebuild scheduled for merge) pulled in by mail-mta/ssmtp
The delayed || evaluation code from bug 264434 should help in solving this bug, since it applies to all virtual dependencies.
Gentoo has recently stopped using old-style PROVIDE virtuals, so it won't be necessary to fix this.