Is there any warning lights "on" on the instrument panel? Check Engine light or any others?
How many miles on the car.
How long ago where these parts you mentioned replaced, and were you trying to CURE this problem at that time, or did the problem START at that time, or did the problem start quite a while after this work was done?
Were the MB recommended spark plugs installed, or did you pick up some type of "super" spark plugs you thought would work better?
Using what octane gas, and is it from a nation brand name or an "off-brand" fuel supplier?
Is it possible that it started doing this after a fuel fill-up, maybe a bad shot of gas, like with water in it? Water can stick around in a fuel tank for quite awhile, it sinks to the bottom of the tank.
Possibly because of the statement that it gets worse as it gets colder it may be the engine temp sensor.
A mechanic could simply install a scanner on the car and read what the engine temp sensor is reading, that's the easiest way to test it.
Did the problem possibly start after the engine was washed down? 104 motors are famous for collecting water in the last few cylinders (6 especially, and sometimes #5) and wrecking the insulators, of course this is usually a constant problem, not just when cold, but it's a thought.