Hi Ben,
Well sounds like you got a wierd one. Some thoughts  for extremely rich:
At start up the O2 is ignored.  Fuel enrichment at start is dependant on
the Temp II, and The TempI, air temp sensor in the AFM.  I had a real
chug chug start up, turned out to be the Temp I sensor was causing it.
Depending on which ECU program, the Air temp sensor affects enrichment
at different ambient air tempatures.  le

A Ecu swap for testing would rule out a rogue ECU issue.

There is an O2 sensor ground fault that occurs occasionaly, the green
wire to the ECU shorts, and needs to be replaced, this would likely not
be a start up issue, but could be a dead short case, not to affect the
mixture whether the O2 is plugged or un Plugged.
Air Temp Sensor in AFM bad.
Bad ECU
Another issue could be the AFM flap or spring.    Spring to loose, or
flap sticking open somewhat, as a guess
A call to Darrell Boheler, via the list would be advisable if you get
enmeshed with chasing ECU or faulty Temp I sensor inputs.

Mark Keller