Firstly I would look for any connectors around the engine that are not plugged in. Check the wiring inside the cable trays that run across the passenger side cylinder head and across the front of the cam cover for damage.
Secondly, a lot of this seems to point to the EGR and air injection systems, and, in fact, if these systems have issues, it may well be causing the Lambda sensors to misread by leaking air when it's not supposed to! So that's most of that depressing list taken care of!
Have a look at the pipework and wiring to the EGR valve on the driver's side of the inlet plenum and make sure it's all intact and not blowing exhaust gas. Do the same for the air injection pipe which runs across the front of the cam covers and back to both exhaust manifilds. Check the rubber secitons of hose aren't split or blowing exhaust gas.
Thirdly I would check both Oxygen sensors, which are screwed into the exhaust downpipes. Make sure their connections are secure.
Let us know if you find anything and we'll take it from there.
Kevin