Interrupt: Need to keep track of time spent in routine or ... ?

I suspect you are doing this:

delay(time1);
output_to_device_1;
delay(time2);
output_to_device_2;

Since you have not posted any code I am guessing.
Have you looked at the blink_without_delay example? This allows several 'things' to go on at once,
with the advantage that the processor is not hung in a delay() statement.

Your structure in that case could be something like this pseudocode,

// need a array of times to do things, what to do it on, which way to switch (on or off)
// a structure might be a good way to do this, you could probably get the (time, device address, operation) into
// ( a byte, two bytes, a byte), so for 500 devices would take 500 * 4 =  2K of program memory

void change_output_to_off(int current_step)
{
  // look into your sequence array, choose the device indexed by current step
  // and turn it off
}

void change_output(int current_step, boolean fault_found)
{
  if (fault_found){ return; }
  // look into your sequence array, choose the device indexed by current step
  // get the desired value,
  // do whatever address setting up you have to do for that device
  // change the value
}

setup()
{
   fault_found = false;
   current_step = 0;
   // other stuff, including recording starting time from millis()
}

loop()
{
if (!fault_found)
{
   fault_found = check_fault_state();
}
if (fault_found)
{
  change_output_to_off(current_step);
  if (time_elapsed_after_fault(millis())) 
  {
     fault_found = false;
  }
}
if (time_to_do_next_step(millis())
{
   set_up_delay_to_step(millis(), current_step); // sets up next place to synchronise from array of devices and times
   change_output(current_step); // this drives output if there is no fault
   current_step += 1; 
}

}