There are two things that can cause overheating:

1) The heat generation system (engine operating) adding more heat than normal.
2) The heat removal system (cooling system) not removing heat fast enough.

I think the key here is the cold air from the heater. If there was something causing the engine to run extra hot, the heater air would be even hotter.

Since the air from the heater goes cold when the engine overheats, it appears the coolant stops circulating for some reason. A thermostat stuck shut would cause overheating, but the heater air would still be hot.

Possibly an intermittent water pump issue?

Or maybe a piece of debris fell into the water jacket holes when the head gasket was replaced, causing the debris to jam somewhere once in a while? You said the dealer found debris last time and had to backflush. What are the odds all the debris was cleaned out?

Something drastic happens sometimes, since its either running fine or overheats badly.

Steve

 

Eight Good Sams try to help. No good deed goes unpunished.

 

Thanks Steve

 

"I did notice residue in the antifreeze that looks very similar to “Bar’s Leak block seal”" - if it is Bars Leak as you suspect, that indicates a serious problem that was being covered up,
and likely will need to be diagnosed by a good mechanic who can actually lay hands on it.

If it is in fact Bars Leak, I'd be knocking on the door of the place that sold it to you asking for your money back - as they scammed you.

 

Just as a side note.
How about water pump cavitation ?
Yes no heat from the heater core would lead you to air in the system.
I know this can be an extreme, but it's hard to diagnose thru the internet at times.

 

In post #12 it is stated that the cooling system has been burped.
What looks like Bars leak could be crystallized Dexcool, it does get that way after being overheated that much.

 

if it’s had Barr’s leak used it’s possible the heater core is partially clogged. This will cause it to over heat also, easiest way to diagnose is to use 18” of 5/8” heater hose to bypass the heater core near the thermostat housing. If that’s it the engine temps will remain low and stable.