In his book Annapurna: 50 years of Expeditions in the Death Zone, Reinhold Messner relates how the first party to ascend an 8,000 meter mountain made "tea on the alcohol stove" the night before the "assault". At way over 20.000 ft. it was very cold on that trip - Herzog and Lachenal both came back with critical cases of frostbite.

I have used alcohol stoves in conditions as cold as negative 30 degrees and at 18,000 feet elevation and haven't had any problems.