Can you try to set the MAC address by hand with the completely patched
kernel (i.e. including the mac-address-change patch) ?

Yup. Works fine. The randomly changing interface order is proving to
be a challenge!

Given the last report in http://bugzilla.kernel.org/show_bug.cgi?id=6032,
it should be straightforward with your Debian system.

No clear idea why your three cards are not handled the same though.