We present a new retrieval technique for mesospheric measurements from the Halogen Occultation Experiment (HALOE). Previous HALOE retrievals did not account for polar mesospheric clouds (PMCs) and were biased whenever PMCs were in the sample volume. In the new algorithm we eliminate this bias by retrieving and correcting for PMC extinction, and we optimize the algorithm for this region of the atmosphere. We have reprocessed over ten years (1991--2002) of HALOE data with the improved algorithm, yielding nearly 75,000 vertical profiles of temperature, H2O, O3, NO and extinction at five infrared wavelengths. In this paper we describe the new algorithm in detail, present several examples of the results and discuss some initial validation and quality assessments.