If the temp on the outlet side of the heater core is noticeably cooler then the inlet side as you stated earlier then your heater core is clogged. Altitude is probably coincidental. Replace the core. Especially since you have verified that the valve is good and the servo is fully opening and closing the valve. The fins could be clogged with dirt but honestly if they were clogged you would have cool air but the outlet pipe of the core would be just as hot as the inlet.
