lucy24 - 9:12 am on Nov 11, 2012 (gmt 0)
page that they tried to access was moved a long time ago.. years even.
Moved-- or deleted?
If the page was moved years ago, but it's the same page, it should have been a permanent, one-on-one 301 to the new page all along. If by "moved" you really mean REmoved, taken away, gone, that's a 410. Google doesn't approve of mass redirects to a single page.
You can achieve exactly the same result by making a custom 404 or 410 page for humans that gives all the same information and has all the same links as a "real" page. But on paper you're returning a 410. And that makes the search engines happy.