BLACKJACK-
If you can speak to the person who you got the engine from I would also ask them if the block was ever filled - drag racers sometimes put a material in the cooling passages of the block to stabilize the cylinders when wall thickness is questionable.
This will affect how much coolant can circulate through the block and will have an effect on how well it cools - in fact it would behave in much the same way you are describing.
While this is only a POSSIBILITY, it does make the thought that you have to replace the water pump seem much more palatable, doesn't it?
