Has anyone suggested replacing the main fuel pump relay? These relays usually cause starting trouble when interior temperatures are high, but it the relay is bad it could cause intermittent problems such as you describe, especially considering the miles. The relay is under the dashboard.
Of course, that assumes a fuel issue is causing the starting. You seem to have covered the spark side.
When the engine stalls several lights should come on. Do they, or is it just the CEL?
When you turn the key to "on," before you start the engine, the CEL should ALWAYS come on. Only when you start the engine should it go off. If it stays on after the engine is running, then there should be codes stored.