Update:

I went to the local Auto Zone on Sunday and bought the sensor. It was about $20 with tax. It looked like the OEM unit, but a little longer (the thread area I believe) and no stampings of any kind. Took out the old one, which is really easy to get to BTW. With the new one, I needed more force to get it all the way in. But I did not use thread sealant or whatever is supposed to go on there. Right now, I can see about a quarter inch worth of thread sticking out...but no leaks or anything. The clip on the wiring harness broke as well (dried up plastic) but the harness connector still does its job.

So I've been driving the car for 3 days now with the new part and my idle has been perfect and the car has started every time! I think it is a little smoother too. It just might be that this one piece was my problem. This is why I bought an OBD2 car...so when something fails...the car will tell me. It is just that I had to wait for a while to get the part to fail and register with the ECU!

I reset the check engine light last night and of course will have to drive for a few more days to ensure the light does not come back on and that my issues really are resolved.