Gate drive of 12 V should be enough to saturate any MOSFET. have you scoped the drain voltage yet? Is the drain voltage doing something silly, when it's supoosed to be down at deck?
Some circuits, if you're driving the gate with something weak like a 4011, it ain't a strong enough drive. CMOS output drive is fine for switching lamps and relays, but not for most PWM. What can happens when you try turn on the fet (especially with high voltage on the drain), is as the drain voltage flies down, a current pulse gets coupled into the gate (via the drain / gate capacitance), the opposite of what you are trying to do and then the fet turns itself off for a while as the capacitance charges. Result warm fet.
One way you can bolster up the drive is to connect a wad of 74HC244's in parallel as a gate driver. Or use a TC4427 like blueroom suggests (easiest)