Way back in the early 90's I was flying DC-8's. Flying in and out of Saudia Arabia during Desert Storm/Shield. On a ferry trip back west across the Atlantic we were at Fl 410, max certified altitude. Half way across we ran into a temperature change. It started warming up and we had to increase power to maintain cruise mach. We finally had to go down to maintain speed. Not what you'd expect....