Yep. Vgs did it.
I've got a n-ch MOSFET P/N MC7812BDTRKG (Digikey link) hooked up for reverse voltage protection (see attached).
I think you got confused. MC7812 is a 12V regulator. But later you linked to a IRML6344PBF mosfet, so I think you just got confused here.
When the mosfet is fully turned on, as in your case, then the Drain and Source are almost at the same potential. So Vgs is equal to your power supply voltage, minus the voltage drop Vds, which is Vds = ( Rds(on) * Iload ). This will be small since Rds(on) is small. So Vgs is always running really close to your supply voltage here.
The solution is to put a 10k resistor in the gate, then put a 12V zener diode across the Gate and Source pins. Vgs(max) is 12V on that device.