2000 Mazda Protege car dies when warm

This car has had this problem pretty much since I got it ~1yr ago. It dies after it stays warm for a while, running the heater at full blast seems to extend the range a little bit, but it mekes me kind of uncomfortable.

The mass air flow sensor was covered by an extended warranty, and was supposedly failing (per the engine computer's codes), so I had Mazda replace it.

problem persisted

took it to a shop to diagnose, they said the downstream o2 sensor was faulty and the catalytic convertor needed to be replaced, projected cost was nearly $1000 (OMFG WTF?)

I replaced the o2 sensor

problem persisted

removed the catalyst from the catalytic convertor (I may put a cheaper one downstream later on.) Catalyst was grey and melted, obviously shot.

car ran a little better, but still the problem persists. Reset the computer, engine light stayed off untill the car sputtered to a pathetic death as I barely got it off the road into my driveway today.

Now, I ask would it help to put in a another new downstream o2 sensor, assuming the first one I put in got burned while living behind my shot catalytic convertor? Any other areas to check on that could cause this kind of behaviour?

why would a faulty o2 sensor cause a car to die, seems like a flawed design. Old cars didn't have these, it should not be essential for the car to run right? I thought o2 sensors existed to limit emissions and to maximize fuel economy. Shouldn't the computer default to a less efficint operating mode instead of dieing all the time and leaving in the middle of the road waiting for the stupid thing to cool off so I can use it again?