Just circling back with my final solution. After thinking about the second-wall-wart idea, I abandoned the idea of using a DC signal to detect a utility power failure. Until I put the thing in practice, I probably won't have a feel for how brief an outage I'm actually interested in detecting (but below some minimum, I won't worry about it). With a wall-wart, there are filter capacitors involved, not sure how long they'll last, the MCU pin is effectively no load, so need a resistor to load it, have to figure time constants, etc. etc.
Much easier with an opto-isolator where the LED is driven direct from the AC line, using the circuit I posted earlier in the thread. I think this is quite a safe circuit, and of course it effectively keeps the mains voltage away from the MCU, etc. Connected the collector from the opto transistor to the INT0 pin and turned the pullup on, so while the power is on, it'll generate 60 interrupts/second. The main loop simply counts milliseconds since the last interrupt, and compares it against a threshold value, so very easy to change, and easy to set quite accurately. The ISR is one line of code, simply setting a variable to zero, so very minimal impact to other processing.
It's running as I write this, counting cycles per second, mostly giving a boring string of 60s, but it gets interesting once in a while. I just saw a string of 12 or 15 61s in a row, with a couple 63s or 64s thrown in. Also see the occasional string of 59/61 pairs which is probably just random phase synchronization between the MCU clock and the line frequency. I've heard that power line frequency is very, very accurate over the long term because they count the cycles and adjust accordingly, but it can be off a bit at any point in time. Looks like that is indeed the case given my small sample here.
