People tend to notice whether the power is off. Have them use their phones to report it to your own web site, with the server on an uninterruptible power supply.
Have a small lamp connected to the power grid and an LDR attached to the Arduino to detect whether it is lighting. The Arduino will need battery backup.
Or, if the backup battery is trickle charged from the power grid the Arduino could monitor the low-voltage charge voltage to detect a power outage.