Bit of misconceptions creeping in.
All-moving tailplanes actually create a larger angle of attack at the tailplane than a fixed tailplane. So they can be actually MORE at risk of stalling than a fixed tail of similar size and location.
[Say the aircraft angle of attack is 5 degrees and the downwash is 10 degrees (a lot of flaps deployed!). Then the flow at the tail is 5 degrees downwards, and with a tail fixed at zero degrees on the aircraft the angle of attack at the tail would be -5 degrees. That generates a certain amount of down force and hence nose-up moment for the aircraft. Say I need more to trim. On a fixed stab aircraft I move the elevator, but the tail is fixed so the AoA at the tail doesn't change. On a moving tail I move the tail nose-down - which directly increases the AoA at the tail.]
The tail on an all-moving tail aircraft usually isnt deiced because:
1. Usually you have powered elevators which makes the problem of tail stall less severe and easier to design against (no control 'snatch')
2. Its hard to get anti-ice bleed to the tail because it's moving around
3. The aircraft is certified assuming ice on the tail - basically, the tail is made big enough to avoid the tail stall problem.
Exposure isn't a factor - if you are approved for flight in icing that includes holding, so the ability to "climb through" the ice isn't a factor in the design.