Hello Denn,
It seems that you have ruled out all possibilities except the external EEPROM approach. My personal choice would be to use a serial EEPROM with SPI interface, rather than IIC type, as Jim D suggested. The SPI interface is faster and simpler.
If write endurance is an issue, I might alternatively consider a FRAM device. These also have the advantage that writes are as fast as reads.
If your critical interrupt processing takes a substantial portion of the available processing time to complete, this does mean that any other interrupts, that may be necessary, will mostly be delayed until the critical interrupt completes. Their ISRs must be very short so as to have negligible effect on the next critical interrupt that they may possibly delay.
It is also possible that the use of any other interrupt may be impractical, in this case. For the circumstances you have outlined, I think you will need to become aware of the exact worst case ISR processing period, which should also include the amount of delay that all other ISRs may introduce.
A final suggestion if you are programming in C - if the critical ISR code should contain any switch statements, replace these with if / else if constructs for faster code execution.
Regards,
Mac