Usually a sticky thermostat would cause this but you have already replaced this with a new one. Have you inspected the drive belt for the water pump? Could be that when very cold this may be slipping. The only other place where I have run into this is when I had a harmonic balancer pulley outer ring not bonded to the inner housing. Slipped alot when cold and then when warmed up the friction was better but not 100% so it would drive the belt. Never heard any squeeling at all. The only way to verify that would be to remove the belt and try to turn the pulley with your hands. It should not budge.