I don't really know as much about this as the others, but I'll throw out some ideas:
-Check with a vacuum gage while running. I don't remember a lot of details, but you can tell a lot about engine health by how the needle moves- I would do a thorough test for vacuum leaks as they are common on these engines. As they tell people in medical school- an uncommon manifestation of a common problem is more likely than a common manifestation of an uncommon problem. If you hear hoofbeats, think horses, not zebras.
-You said it was rich, but I didn't see black smoke in your video or any significant amount of soot on the exhaust pipe. Can you smell raw fuel (either rich or poor atomization), or can you smell NOx (raw no-cat exhaust smell- somewhat normal on cold starts since cat is less effective cold, but an excessive amount of it, especially while running hot, might suggest a lean condition)?
A vacuum leak would probably be a lean condition, but weird stuff might happen when the computer tries to compensate for it (surging, sputtering, etc.). Vacuum leaks could come from a lot of places- intake gaskets, brake booster, hoses, etc. and electric/vacuum devices like EGR valves
