Well, this is getting interesting ... I ordered the new HO2 sensors last week, and was gonna put them in this coming Saturday .. the CEL is back on (after I cleared the codes).
On Sunday (i.e. last Sunday, after I got the parts but before I've had a chance to put them in), my wife tells me that she was at a stoplight, the car suddenly shuddered quite noticeably for 3-5 seconds, and then the CEL went out! And it's stayed off since then.
So for now I'm gonna wait and leave the parts in their boxes ...
This is very weird ...