netmeg - thanks, do you mean 'disappear from search results' or 'disappear altogether'? The former is easily done, the latter rather less so. I'm also now pretty certain that a 301'd page that was previously indexed will still be retained in some form within the google index, even if it doesn't appear in the results.
leadegroot - yes we did 'Change of Address'. Didn't make any difference. Interesting that you are getting requests for pages that have been extinct for ages.
The only thing I can say with certainty is that pages will stop showing up as incoming external links to my core domain if they return a 410 enough times (or NoIndex). The question is then whether they'll still be harming my organic rankings because of duplicate issues.