Kinda sounds like your O2 sensor is misleading you. Sounds like you're getting an idle misfire/partial misfire for whatever reason (possible too rich), which is putting unburnt O2 down your pipe.
I'm going to post my .msq and screens of the key parts later tonight when I'm home. Mine seems to be different from the one's I've seen, and my plugs come out spanking clean every 3k miles.
Joel Baldridge, ASE Certified Master Technician, Audi Certified Expert Technician