From my understanding millis don't work we'll in interrupts.
It works just fine. It simply returns the same value every time it is called in the same interrupt, but the value is correct and meaningful the first time. Calling it in different interrupts, and determining the time between two interrupts is quite possible, and even easy.