Hello,
I have a low cost idea, install an SCR between the voltage regulator and the load (PIC) make sure the filter capacitor is on the load side of the scr. Using your existing relay setup the SCR will disengage when power is cut off to the SCR and will not reapply power if power supply should power up again,bias the gate so it requires a significant voltage to trigger it to prevent Ghost startups, otherwise a simple latching relay setup like power tools use would do as well.