I have had problems starting my 1999 E-320 for almost a year. I noticed that when it is wet outside (winter) when I turn the key the starter will staret to turn the engine and then quit. If i turn the key all the way off and then all the way back to "satrt", the starter will usually work after the 3rd attempt.
Someone suggested that the Bendix (the part of the starter that spins out and engages the flywheel) needed lubed. I lubed the bendix and for goo measure, i put some grease on the flywheel teeth.
This seemed to instantly stop the problem for several months. Suddenly the car started doing the same thing, but after three or four attempts I got nothing out of the starter. Since everything in the car worked electrically (headlights, radio, windows etc) and battery voltage read 12.2 volts with a digital volt meter, I seriously doubted the battery. However, when i jumped the battery, the car instantly started. The car then worked great for sever weeks and then suddenly, the same thing, I checked voltage, got above 12 volts, jumped the car and it started fine. After the 3rd time i took the battery to Autozone and they tested it. The tester said "charge and recheck". I left the battery for an hour's worth of charging. When i returned they told me the batter got very hot ans stinky during the charging so they had to pull it off the charger.
I left with a new battery and wow did it make a difference. The car starts every time and i noticed a signifiant difference in the speed of the starter motor.