I had this behavior on an old 164E with a failed fuel pressure regulator (stuck so pressure was too high). The fuel pump was the original. I surmised the fuel pump was bad so I put in a new one. With the new pump the car ran worse. I assume the old pump was weak, so the engine ran ok much of the time. With the new pump, but still having the bad regulator, the mixture was very rich, due to more consistent and higher pressure. Car was then very hard to start. Plenty of black smoke in the exhaust. A dealer shop diagnosed the bad regulator.

Also possibly bad ECT sensor or loose connections to it.