For the symptoms you describe, the most likely failures, )after a fuel system relay, which you've already replaced), are the hall sensor and the radio suppression relay.

Next time you have a no start, watch the tachometer as you crank. If it bounces off zero as the engine cranks, the Hall sensor is likely NOT the problem. If it just lies there, then the Hall is the most likely candidate, and you should perform some standard ignition system tests, like checking for spark when you're in the no start mode.

If the tach bounces, the most likely next candidate is the radio suppression relay, and one that fits with the bang you described. The RSR (which really has nothing to do with the radio) provides the positive signal to the injectors, and can fail intermittently because of poor solder connections. When it does at cruise, it can cause a backfire. The RSR, a little black box relay, should be mounted on the passenger side of the engine compartment, just forward of the shock tower.

A simple test, again, when the car is in a no start mode, is to put the tip of a screwdriver on the relay, your ear on the handle of the screwdriver, and have an assistant turn the key to the on (not start) position. You should hear a noticeable click as the key is turned on and off. Another test, again with the key in the on position, is to put a test light on the lead to an injector. If the light doesn't light, most likely culprit is the RSR.