Hi Hedgehog, given this forum is for 'The Pacific' region my comments were somewhat related to that context. My flying experience has only been in this region so I don't claim to offer any special insights for your scenarios.
If you are in a pressurised turboprop I would have thought quickly out climbing the ice would be the way to go in most cases. In some ways the 'climb performance' problem could be worse in 'warmer' climates with ISA + temperatures where the freezing level is a lot higher and the ice forming then also happens at higher altitudes where the aircraft's performance also reduces.
Generally there are to escape to warmer temperature in this case, one has to descend pretty low and since it is mountainous it would be difficult to descend that low and maintain MEA or even be on minimum vectoring altitude. If you are not sure of your climb capability and have to descend to get the ice to melt off (I have heard of 3 inches of ice in a minute in a Super King Air so it gets really hardcore around here sometimes), then what would be the next step if you would end up below MEA and vectoring altitude at that point while on IFR plan. Does it mean scudrun to destination necessarily?
This does not sound like a situation I would want to be in. If you are IMC below MEA without the ability to climb you are in a dire situation - an accident waiting to happen. Leave the scudrunning idea for the young and the bold...
The step climb is something that can work. I have used it more in the mid to upper 'twenties' flight levels. You may be able to request a 'block' altitude also (check your alphabet airspace rules). I know of people also choosing to conduct a steep descent (as opposed to a standard 3* profile) to minimise their time in weather/icing on descent. Beware of speed considerations if expecting to encounter turbulence as well however.
Have not had to deal with freezing fog but would offer the following. Check the aircraft's pilot operating handbook as there may be specific information and instructions regarding this. For example, this is stated in the icing limitations section of one pressurised, 'all weather' de-ice equipped turboprop:
Flight in freezing rain, freezing fog, freezing drizzle and mixed conditions causing ice
accretion beyond the protected areas of the pneumatic boots is not approved.
The aircraft must be clear of all deposits of snow, ice and frost adhering to the lifting and control surfaces immediately prior to takeoff.
Some aircraft are better at 'carrying ice' than others. Talk to others who have done what you are doing and learn what you can about the aircraft and it's behaviours. Find out their 'local knowledge' weather tips for regions and routes that you will be flying. Sift the information and add it to your bag of knowledge.