I have finally found what was wrong with cairo and the bad alpha blending. Cairo supports ARGB32 surface, but only with premultiplied alpha. That is, every component of a pixel is stored premultiplied with the alpha component.
I have not found an answer for this over the internet, and I assume premultiplied alpha is not suited for the type of operation I'm doing. I switched to PyQt4, used ARGB32 images without premultiplication, and it worked like a charm.
I also tried with PyQt4 premultiplied alpha images, and reproduced the problem.