"...Okay, I put the car into the run position, cleared the code, and turned it off..."

Let me try that again......

AFTER you've cleared the code and turned it off, turn the ignition back on again but DON'T start the engine. Leave just the ignition on for several seconds. The sensor pre-heater should be trying to work as long as the ignition is on, even though the engine isn't running. (At least that's what I seemed to observe.)

So after the ignition has been ON for several seconds WITHOUT the engine running, turn the ignition back OFF. Now connect your scanner, turn just the ignition ON and read the codes. Note, you never start the engine this whole time.

The only point I'm trying to make is that in my case, I was able to re-assert the pre-heater fault code without even starting the engine - just by turning on the ignition. I don't know what year, etc, your's is, but it might be that it doesn't power up the pre-heater until the engine is actually started. Also, in my case, the car ran perfectly fine. It just kept recording the fault code each time I turned the ignition on. A new sensor cured it.

It's really sounding to me like you need to R&R the sensor.