You know, the other thing that occurs to me is that recall that was done to add another valve between the block and the heater core, something to do with limiting pressure to the heater core so folks wouldn't have their legs scalded in the event of overpressurization of the cooling system... anyone remember the details of that, and do you have that valve in the path between the block and the firewall?
I also found a magazine article I saved from somewhere that shows how to rebuild the heater valve; unfortunately, I have no means of hosting the file, so if you would like it, send me a PM and I'll try to email it to you.