So, when does the device actually fail from overheating?
When the silicon temperature exceeds the maximum. This is not case temperature.
In general for every 10C rise in temperature the expected life time of a semiconductor device half's.- brownout when shutting down (can this demolish the chip?)
NO- overcurrent on i/o pins, they are not protected by a resistor
Only if the design is wrong and then I would expect to see just the output pin go not the whole chip. I expect the chip is dead as it won't re program.- overheating atmega (through overheating the regulator?)
one does not follow the other, an overheating regulator should just shut down. It can overheat the whole box but that depends on how the box is physically constructed. Do you have any air movement over the electronics?