If you are running overly rich, it will as you mentioned, cause a black sooty covering on the outside of the sensor. If it's caked up enough, it may also cause the engine to run even richer by causing a mis-reading in the sensor itself. The heating element in the sensor might have gone bad, and because of their location they need it to function properly. From your description, the ticking noise was probably coming from the cat too as it was expanding due to the extra heat it was generating.
I'd check the sensor again in about a week, and if it's dirty again I'd try replacing it. Either that, or swap the sensors left and right and see if the problem follows the sensor or stays on the same side. If you are going to replace the cats, I'd wait until after the fuel problem is solved. That way you don't burn up another one.
My oil line fix
My 100k stopped odometer fix
Brace for impact, I'm in a "modifying mood". Massive thread count inbound.