I waited for someone more knowledgeable to respond, but seems that you are
at your wits end, so I'll throw in my 2 cents.

An 'always rich' condition is unlikely to be due to a failed sensor. Guess
that at least in theory it could be due to a short between the HEGO heater
power and output wires, but that's about it. And since you already replaced
the sensor, we can safely rule that out.

I would look for the following:
* Leaking injector or something causing an injector to be constantly
energized (a short in the harness, PCM failure)
* Excessive fuel pressure (faulty regulator)
* Some obstruction in the air supply, like a clogged filter (but that should
have been sensed by the MAF if functioning properly)
Much less likely:
* A short or cross between the power and signal lines between the PCM and
the HEGO sensor (if  the harness was damaged or modified in some way)

I am sure there are quite a few more. Let the experts speak!

Good luck!