Nissan Repair: 99 altima no heat at high speed

Question
Hi.
I have owned this 99 altima gxe automatic transmission for almost six years. Probably around 130,000 miles this problem began occurring: The engine heats up, the gauge on the dash indicates this and it gets to what would be a normal operating temperature. This takes probably about ten minutes on the cold days. Once I start driving it, less and less heat will come out, and it eventually turns to barely warm (but still slightly warmer than outside air temp). The fan blows at all the different speeds, and the higher the blower is set, the faster it cools down to below the lowest mark on the temperature gauge, and this is dramatically increased with an increase in speed. Going about 25, I can get decent heat, but if I get on the highway, basically there is no heat ( maybe lukewarm air). What might be a good first step in diagnosing this issue?
On almost all the forums, people are having the exact opposite problem, that at idle or lower speeds they get no heat, but once they are traveling at faster speeds, the engine is working more and they are getting heat, so it seems like my problem is less common and no a lot of information out there on the internet.
Thank you

Answer
Hi William -

Check 2 things:

See if the valve is getting hung up. If you follow your heater hose, you will find this valve in line and it is usually run by engine vacuum. Perhaps the hose is broken and you are losing vacuum at higher speeds which closes the valve.

The heater core in your vehicle may be clogged. Usually located passenger side above the floor near the glove box. Looks like a mini radiator

Hope this helps -
aloha
Calvin