I'm still not understanding something...
When the thermostat starts to open, just enough coolant begins to flow through that the thermostat will not open any further, establishing a temperature equilibrium in the engine (I know this, I've tested thermostats in hot water and watched them gradually open & close as the water is heated and allowed to cool).
What you're saying is the thermostat just "pops" open and the whole entire shebang in the radiator flows into the engine all at once?? (is that what you mean by "going through the warmup cycle all over"?) If that were so, that would lead to a cracked block in very short order (at least I was always told by many when I was younger to never ever put cool water into a hot radiator unless the engine is running because it could crack the block after you start it).
I'm not saying you didn't have an issue, I'm just trying to wrap my head around how the radiator was the cause of it, and not something else.
I will admit, I have not been in temps below around 5°F, so maybe there is infact something there, but I having a hard time theorizing what or where it is that would cause it if it wasn't just the cold air blasting against the engine itself.
Also, MPGs will drop in cold temperatures simply because cold air is denser & heavier than warmer air (though I would agree, probably not from 19 MPG to 12, maybe more like to around 16)