What about the thermostat in all of this? Has that been considered or changed?
Thermostat closes randomly, fans operate until the coolant temp in the radiator (where the fan sensor) is located drops and the fan shuts off while the engine continues to operate in the red due to coolant not circulating through the radiator.
If the T-stat has never been changed then I’d throw one in there and see what happens.
Misdiagnosis of head gasket issues is not that rare when it comes to overheating.
Just a suggestion anyway and maybe you’ll luck out here.