I've recently been through cooling system woes (replaced all but the radiator in fact - including heater hoses, heater core, coolant temp sensor, thermostat, etc. etc. etc.). The coolant temperature sensor I bought recently from FCP (roughly 6 weeks ago) failed two days ago. The inner probe has come out of the brass screw-in housing. This is causing the same problem you describe, sometimes it registers the correct temp. and runs well, other times it registers cold - causing rich running, enough to typically flood the engine and prevent it from starting.

I would give the sensor itself serious consideration for being a possible problem.

Also equally likely, check the connections for the plug-ins at the temp sensor. It's rather common for the plug to deteriorate and allow the wires to drop down in the plug housing, not giving them very good contact with the mating wires.