I still think trying another dealership first is the better route to go.
ABSOLUTELY. You need to find a better mechanic. Pronto.
As to it being an emissions control problem, like an O2 sensor, I doubt it. The P5 is an OBD-II compliant car, and a failing O2 sensor will trigger a CE light.
Based on your observation that it does not happen when the fuel tank is full, I would get busy on things like fuel pressure. I'm not sure about Mazda's diagnostic system, but fuel trim is an OBD-II generic requirement, and a rich or lean condition should also trigger a CE light. Now, the system has to exceed a certain threshold before the CE light is triggered, but codes are stored even if the CE light is not lit.
Fuel trim problems make for a stumbling, stalling car, just as you described. I would examine the fuel pump, filter, and possibly the pressure regulator. Could be a metering problem, meaning an Air Mass Meter (Mazda might use a flow sensor, but it's similar) or O2 sensor, but those are usually very sensitive and trigger CEL's fast. If it's a metering problem, it means that the FI system fails to match fuel input and air flow.