Scremando le battute, confermo quanto detto da Testato 
Se il controllo lo fai nella forma
MILLIS - TEMPO_PRECEDENTE > INTERVALLO
non incorrerai mai nell'overflow di millis perché il risultato di (millis - vecchioMillis) sarà sempre un numero uguale o maggiore di zero anche se millis si fosse resettato.