Robin2:
I would run the Arduino from a lead-acid battery...
As soon as I posted my reply above and re-read it, an idea hit me: I could tap off of the battery used for one of my backup sump pumps. It's already there, and it's already being kept charged by that system.
I'd still need a way to detect when the main power goes out, but the USB wall wart into an Arduino pin should do it.