lol....it sure sounds like a sticky thermostat, did they give you the old one?......
if that ain't it it's gonna be the engine controller or one of sensors (mass air, o2,), there are very few things that can MAKE the engine overheat...but the thermostat can stick from crud in the coolant and do this randomly and drive a mechanic half crazy (this one anyways).
When Michigan had the engine pollution testing mandated I had sent the wife unit out to gitter done....I told her to drive it around for at LEAST 20 mins. to make sure it was nice and hot to pass the test (a 1965 100K+ car would pass if hot enough)....she didn't, drove right over and it failed (of course) and the mechanic tried to talk her into getting the injectors cleaned for a discounted $159.95 a DISCOUNT !
I had her come back to the house, pick me up and we would go discuss the dirty injector issue with the mechanic. It was truly a kodak moment when we showed up at the shop....darn it if the car didn't pass that test with flying colors, and didn't seem to need that injector cleaning after all !?!
a 1965 with injectors?
the thermostat would cause him problems much more often.....in my opinion anyway.
if not the cooling fan, or cooling fan relay, i'd want to think that the cadillac asperins aren't working quite right, and every so often, the cooling system is becoming hydro-locked from combustion pressure.