Any Toyota Techs on here?

I mentioned the vacuum idea because of a few reasons. You asked for a Toyota tech. I worked for Toyota in Macon, Georgia for a good while. I am still Toyots certified, as their certifications never expire.

Secondly, I left there in 1994 and at that time, there were some HVAC systems using vacuum.

Third, vacuum hoses, if the HVAC is equipped with them are dirt cheap to replace. I always try to recommend the cheapest thing first, because 1) the cheap stuff tends to break or wear out first and 2) it's cheap to buy. lol

Not all systems will default to the defrost if they lose vacuum......even if they are designed to. I have found that out the hard way. On more than one occasion.

At any rate, after reading everything you've tried, I agree with making sure the pump is flowing good and there is no air trapped in the system. Either condition could certainly cause what you have. Posts 26 and 27 are right on the mark, I believe.

One last thing to consider. If the fan clutch is faulty, it can be faulty both ways. It can freewheel, but it can also lock down as temperature increases. If that's the case, it can actually cool "too good" and cause the heater not to get hot. That's a long shot, but certainly worth checking. The Toyota fan clutches are serviceable. They can be disassembled and refilled with the silicone gel that makes them work. I have seen some so dry, they lock down, rather than act as a clutch. Just something to check.

Good luck!