A similar problem was talked about here. http://www.picbasic.co.uk/forum/showthread.php?t=5649
The question was how to write data as the power was being cut. Same thing but backwards for you.

Use a comparator to monitor the voltage and make your own brown out control.

Use a backup battery and monitor the machine power, when machine power is cut the PIC will then go into a shut down sequence shutting off the battery power.

I think this is the closest thing to "fail safe" you will get, think of a good UPS system with voltage monitoring on a server.