My '91 300E (175k miles) had similiar problems. I was told to run several Techron fuel injector bottles through the fuel system. I had run one about 5k miles before and felt little effect.

So I did. I ran a rich mixture through the system, twice. Cold start dramatically improved, idle rose. I think changed to copper plugs and the idle is now smooth and right at spec.

In a nutshell, it sounds to me like bad injectors, including the cold start. Considering all the other items you have done, injectors are not that great an additional investment. Make sure they are good. Test the spray pattern.

How many miles on your car?