a layer of the paste??? It should be a very thin layer or it inhibits efficient heat transfer.

Where is the fan plugged in??? Is it plugged into a three pin connector on the mobo? That connection is controlled by a chip on the mobo that senses temp in itself and modulates the 12 volts to the fan in a on'off cycle of varying duty cycle. Possibly the chip has failed in the always ON mode.