Here's my current idea for the equipment layout:
The UPS will allow the Pi to ignore momentary power glitches and to shutdown gracefully if the outage lasts more than a few minutes. In case the UPS doesn't signal power failure, the photosensor shown above is a cheap solution.
Everything in the diagram adds up to no more than $300. But the trick to making it reliable will be in the software.