I have elec. Baseboard heaters with double pole thermostats. When you turn them from the "off" position, units immediately come on and stay on.

Has anybody changed ANYTHING in the wiring recently? If not, it sounds like the thermostat contacts have welded themselves together and the contacts on the other leg are shutting it off when it is turned to OFF. Be glad that you have a double pole thermostat. Replace it with the same.