debounce problem

if interrupts are disabled hence millis() can't advance ?

That would be the case if millis() is poorly coded. Interrupts get disabled all the times. millis() presumably is programmed on timer interrupts. So even if the interrupt is disabled, the flag is still there and the timer keeps going, not missing a beat.

However, if one of the isrs takes too long to execute (during which the timer's flag is set multiple times), millies() will lose count.

You can test this by running a loop inside an isr for an extended period (longer than millis()) and then read millis() to see if it is missing the beat.