DillonInCO

It sure sounds like an O2 sensor. I think you need a more specialized scanner to get the specifics on which one it is though. I would see if you can find someone near you who has an SCT tuner (or similar) that you could borrow...those will log data to a PC, and give you sensor readings that should help troubleshoot this.

So many things it could be...found this pretty comprehensive list on another forum, some you've obviously already ruled out though:

Fuel system

- Excessive fuel pressure.
- Leaking fuel injector(s).
- Leaking fuel pressure regulator.
- Low fuel pressure or running out of fuel.
- Contaminated fuel injector(s).
- Vapor management valve (VMV) leaking.

Induction system

- Air leaks after the MAF.
- Vacuum leaks (vacuum lines and gaskets).
- Restricted air inlet.
- PCV system.
- Fuel purge system.
- Improperly seated engine oil dipstick.

EGR System

- leaking gasket.
- Stuck open EGR valve.
- Leaking diaphragm.

Base engine

- Oil overfill.
- Cam timing.
- Cylinder compression.
- Exhaust leaks before or near the HO2S(s).