I had a 94 Camaro vert that I bought new in 94. Every couple of years there was a small metal by-pass hose that would always develoup a hole in the exact same spot. I later found out that the engine was full of sand (from the casting of the block) when I had the same thing happen to a freeze plug. While it was being repaired the mechanic asked how all this sand got into the engine, I had it flused and the problem went away, or so I thought. As several years passed the heater lost more & more heat and though I never took it apart (I was living in S. California) I am pretty sure that the heater core had filled up with sand.
I pulled the heater hoses off and tried to flush it out, with no luck, so based on the fact that I maybe used it 3 times a year I let it go. I think that in the heater core, the coolant comes in on one side & exits out the other. The collant can travel through any of the cooling veins, so you could have 80-90% of the veins blocked & you would still have coolant flow, But not to much heat. I think the only way to correct it is to have the heater core pulled and taken to a radiator shop where thay can pull the side tanks and clean it right.
May not be your problem, but it sounds alot like my Camaro heater. Good Luck.....
Brian