http://fabien.potencier.org/article/72/the-rise-of-composer-and-the-fall-of-pear
You mentionned libzypp and the fact it has been ported to PHP.
How much work would it be to write a PHP extension in order to get better performance with Composer?
As far as I understand the situation, the bottleneck is the SAT solver and I know work has been done to provide a C library just for that. See [http://en.wikipedia.org/wiki/ZYpp#SAT_solver_integration] and [http://www.mancoosi.org/].