Silly question: why not use an off the shelf timer relay?
Is it alright if there's a short delay, before it turns on, say 200ms? I have an idea about using a delayed pulse to turn on the MOSFET, after the power supply capacitor has charged enough. This will reduce the power dissipation in the 7555 circuit. I don't have time to post the circuit now, but here's how to get a delayed pulse.
(Attachment Link)
Thats not a silly question. I guess a bought part is the straight forward solution, but think about all the interesting circuits and follow up ideas which have resulted.

Yes. It would be alright with a short delay before the pulse. I also thought about the idea of delaying the pulse in order to have time to charge the supply capacitor. This doesn't seem to be a concern with the updated design from my last post, though. Since the pulse occurs directly and in fact helps to charge the supply rail.
Here is an updated schematic with your cascode idea. Also, I added a second transistor in order to sink the gate current into the VCC node, so that it can be used to maintain VCC also when the main MOSFET is turned off. This way, I don't need a second high voltage pullup resistor.

With all those parts, do you still even need a 555 ?
The specific relay I have looked at will have a coil current of around 3 mA and a specified "must release" coil current 15% of this, i.e., 450 µA.
That already has hysteresis, so your simplest circuit can be a capacitor with a bleed resistor on the bridge pins.
Or you can get more precise timing with just 2 MOSFETS.
With 2 MOSFETS the ON-OFF transfer can be regenerative, so you get a nice snap-action on the drive.
M1 is a low threshold small MOSFET and M3 is a Mains voltage rated part.
Well, I guess the 555's existence can be debated.

I didn't directly find a simple circuit which suited my requirements without it. Also, since its main purpose is timing, when using the 555 within its specifications, the datasheet parameters and equations can be used to calculate pulse times etc. This gives the circuit some "anchoring" and predictability, so to speak.
I like your circuit with only transistors. This is what I was looking for originally. I guess, though, that the actual timing will depend on the M1 threshold voltage. So it may need to be tweaked.
That already has hysteresis, so your simplest circuit can be a capacitor with a bleed resistor on the bridge pins.
Here is that simplest possible delay circuit. Works with the holding current of the relay.
Very simple, but the recovery time is a trade off of R7 and min relay current. Will be a few seconds, so much slower recovery than 2 MOSFETS.
Nice! The recovery time shouldn't be a problem. As long as the fan doesn't have time to spin down. It should take more than a couple of seconds. One concern is that the capacitor needs to handle some voltage and will be physically somewhat large.
I have drawn up a small board with the 555 solution. It may be a bit overcomplicated, but my hope is that it will work out of the box without tweaking. It contains the timer circuit, the relay and connections for a 3.3 µF run capacitor as well as the motor slow speed winding and neutral. This should allow it to be easily integrated into my existing cooling fan.