There are a few possibilities for low/no heat in the cabin.
Lack of heat rejection from the engine; it's too efficient
, not working hard enough to get hot compared to outside temperature, or the thermostat sticks open so that the block never gets hot. If you read good temperature (80-90C) on the gauge it's not any of these.
Lack of circulation to the in-car heater core; plugged core, pinched hose, monovalve stuck closed or not cycling often enough, or a water pump not circulating water fast enough. Since this occurs at all speeds, let's say your water pump is good.
If it's REALLY REALLY cold outside, the air on the HI setting will be moving across the heater core faster than the water can put heat into it. An example would be idling in -20F; not much heat is being put into the block, and a lot of very cold outside air has to be warmed up to 70F, which is like a 100F change!
If this happens a warmer outside temperatures, like above 0F, it still means that not enough heat is getting to the heater core, but this is NOT expectet.
So, from your post it sounds like restricted circulation through the heater core.
Check the coolant level first because an air bubble in the radiator won't let coolant circulate properly, won't give you much heat, and adding coolant is cheap!
Then, check the monovalve operation. A stuck/bad monvalve (probably), plugged heater core (rare) or plugged hoses (really rare!) can all result in not enough hot water circulation. Another possiblility is an automatic temperature control that doesn't signal the monovalve properly.
Good luck. I'll leave you with this happy thought. The Brits, when asked about their sports cars (MG, Triumph) notorious lack of heating, say there's no such thing as bad weather, just bad clothing! Your MB should do a lot better!