I've ran big blocks in Impalas and Novas, never ever had a overheating problem and it seems that you've done everything possible to fix it.
I go with having the coolant checked for combustion gases, I like the collapsed radiator hose suggestion too. The mechanical obstruction idea is a possibility, but it would have to be something done deliberately or a big chunk of gasket, rtv, maybe an old freeze plug jammed up into a cooling passage.
It might be a bit of work, if the above suggestions don't pan out, look at the freeze plugs on the side of the block, if they appear to have been changed there still might be an old behind one or more of them. Once you get them out, poke around the passages with a piece of coat hanger.
Bob