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
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.