Yup, I forget the effects of running rich. That will leave soot contamination on the O2 sensor, not to mention the catalyst.
You're right that there really aren't any moving parts to wear out in an O2 sensor. The problem with contamination comes with the high exhaust temperatures, which in effect bake contaminants on the outside and kill the ability of the sensor to make proper signals. Even without that, heat can change electronic properties over time.
The older one-wire O2 sensors are actually pretty cheap, typically $30 or so. The newer 3-wire sensors, which contain provision to heat the sensor when the car is first started, are the expensive ones. New cars use the preheat jobs, which is why these sensors cost $100+. You can thank the feds for this state of affairs, by the way.
A few years ago I tried cleaning O2 sensors after removing them with a strong solvent such as Berryman's B-12 Chemtool. The sensors had no visible contamination, but the B-12 seemed to help for a short while. I doubt that the B-12, strong as it is, would help on baked-on contaminants.