Has the heater matrix been cleaned out & checked as well & are the operating rods operating correctly? The matrix is constantly hot & the cabin heat controlled by airflow via the various flaps. These along with all the foam seals being deteriorated in the heater casing will drastically affect its performance. A fiddly job to put right but extremely worthwhile.
Also check under the dashboard behind the shin bins (storage lockers) for the aircon integration ports. If no aircon was fitted then they were taped over but the tape falls off over the years & allows great amounts of cold fresh air to flow into the cabin.