The Icemist tribe were a group of tauren that lived in a single place in Northrend. At some point in the past, they colonized a small outpost in the Dragonblight near the border of Lake Wintergrasp and called it Icemist Village. The tribe would not enter the blight proper very often. They preferred the cold of the lake to the bitter air of doom and death of the blight. The tauren were friendly and would supply food, drink, and clothes to those in need. They would help desperate and injured travelers they found out in the wilderness.
It is unclear when the "Icemist tauren" first colonized Lake Wintergrasp. It is possible they colonized the village as tauren, but later evolved into taunka. It's also possible that the Icemist tauren shared the village with the taunka merging into their clan between the time of Lands of Mystery and Wrath of the Lich King, or maybe the Icemist tauren, also referred to as winter tauren (the taunka are referred as winter tauren as well in several quests) were always Taunka, just referred to as different names. By the time of Wrath of the Lich King, the town has been destroyed and Tundra Coldhoof is nowhere to be found. It has a different chieftain, the taunka Roanauk Icemist.