Everything has resistance. Junction (of semiconductor) to Case, Case to Ambient, Heat sink to ambient, thermal paste... All add up to a big resistance of transfering heat from junction to the nearby air.

Adding a thermal paste does the opposite of what you think it does! The proper use of thermal paste is not to make a thick layer between your part and the heatsink but to just fill the tiny holes of the metals surfaces, so you do have more contact area.

The technique is to spread some paste and then with some tool (e.g. a spatula) to remove the rest, leaving only a very little amount in the areas the may not be very smooth (either TO-220 part or the heatsink).

As I have noted on other thread, you need much larger heatsink (around 2-3°K/W) for the losses you have. Or you can add a decent fan (mag lev or with ball bearing) to last longer. In a similar case I opted for a lower cost fan but with 3 wires. The third wire is the internal sensor of the fan and I check it with the PIC. If the fan slows down or stops completely, then an alarm is triggered and the device stops operation to avoid any damage from excessive heat.

You have to either add a bigger heatsink, add a fan or lower the power losses (by lowering the input voltage to the regulator. Or select a SMPS and never worry about heat, heatsink, fans etc. I think it may cost less, even though is a bigger circuit.

Ioannis