If the pressure fail safe really is the key to the problem, I'd wonder if the pump's intake screen got blocked a bit and now it's hard for it to generate nominal oil pressure when cranking to ground the fuel circuit.
I guess you'd have to get a gauge reading right off the sensor port and see....wait, that's what max said, huh? Smart dude
