You need to slow down the turn off of the mosfet or control the rate of voltage change over s-d at turn off to give your protection diode time to turn on. Using the 74AHCT125 which is a push pull driver lowers the gate voltage very fast this turns off the transistor fast leading to a large fast voltage spike from the solenoid or even from stray lead inductance.
Remove r1 and add a series resistor between the output of the 74AHCT125 and the mosfet gate start around 4.7k this will slow down the turn off and on of the mosfet.
Normally mosfets are set up to switch very quickly to reduce the amount of time the device spends in the switching region in order to reduce power dissipation. This is important for some applications where it is switching many thousands of times a second. For your application it does not matter as you will be switching a few times a second at most.
Another method of controlling the voltage spike is to wire a snubber across the s-d of your mosfet. This consists of something like a 100ohm resistor in series with a 330nf 100V capacitor, again you are not switching this on and off rapidly so there will not be a lot of power dissipation.
If the coil is a dual winding flipper solenoid with a separate pull in and hold winding and a limit switch to turn off the pull in winding you need to ensure there are diodes across both windings. If there is not a diode across the pull in winding you will get arcing across the limit switch causing all kinds of nasty spikes on your drain.
Those interested in the suitability of 1N400X diodes as clamps should look at http://www.cliftonlaboratories.com/diode_turn-on_time.htm. I have been using them in this application for 40 years.