If the EGR was sticking open the engine would run real bad at idle. With that many miles it time to think about replacing the O2 sensors. There is a test procedure you can run it through that on the web (can't find at present) which requires removing the sensor, heating it with a torch and scoping it. If the sensor is working OK, the problem may still be lean condition caused by bad gaskets in the intakes, etc. You can find a ton of posts on this bug. I had one caused by a torn PCV hose on the cam cover.
