Thanks for the input, folks!
So you'd expect a 'cold water decoke' effect if the liners were leaking? There's certainly no evidence of that. The varnish under the gaskets seemed like evidence of big leaks to me though.
Also, I was thinking we should have the heads skimmed anyway. It's been suggested to me that we need to get the inlet manifold skimmed as well, so that the ports line up (although even a very heavy skim is only about 1mm, and I've read that the composite gaskets are thicker, so it should just about cancel out.)
The car's got a pretty hefty history folder, with lots of engine work, including a new cam. Don't think there's any for the head gaskets, so those could well be the originals (car's done 120k).
I'd have to say I'd be nervous about buying a 2nd hand engine, as it could have the same problems, although if it's a known good one, it's certainly an option.
...and I have some annoying newbie questions...
1. Head bolts - are they reusable, or stretch ones (I think they're stretch and we need new ones, but no sense in throwing money away if we don't have to)
2. Tab washers on the exhaust manifold - are they needed? One exhaust manifold had them, the other didn't.
3. Is there a limit of how far we can skim before valve-piston clearance is a problem?
4. What's the opinion on the outer row of head bolts on the Pre '95 MY engines - leave them out, put them in finger tight? Do the composite gaskets have holes for them anyway?
5. The push rods got mixed up - I guess we need to check valve clearances - is that right?
6. What's the best method of cleaning the block face? I've never done an ally one before (lots of ally VW heads on iron blocks, but not ally blocks).
Thanks for any input... I really wish I'd paid more attention - all those times I was at the v8 line and I haven't got a clue!