I literally stumbled upon this bug report with LXC, where the network bridge takes the mac address of an interface if the mac address is numerically lower, and this causes problems if that instance is shut down. I think it may well apply to nova?...
(Be sure to open up the comments!)
The workaround seems to be to try to generate a mac address with a high first byte eg 0xfe.
We use 0x02, which is highly likely to have problems (in the same way that 0xfe is unlikely to!)
mac = [0x02, 0x16, 0x3e,
I think this could be related to Bug #908194, but I don't really understand the proposed workaround there.