The issue seems to have been related to clang. I was using clang 3.6, which is the current default version on Ubuntu 15.10. Playing around with clang-3.7, ld.gold and combinations of different tags, all ended with different problems.
On the 4.9 branch (currently tagged 4.9.2-release), I finally built with the default ld.bfd and clang-3.5 (having fixed this bug as well by cherry-picking this and this) and the particular problem above is no more.