Cycle of incorrect pages

I've been doing some work on softtester and noticed my page errors table was 80mb, I was shocked.

So I picked one record, one from an actual user, not a robot. However both are the same in this discussion.

The record shows a page which doesn't exist, correctly.

However, google and other sites don't get a 404 error, they are presented with a search script which provides them with alternative results.

In this case, its presented with 1 search result of the page they were looking for, however this record was deleted some time ago and a re-submitted program / accepted program is been shown. However this new program although with the same name has the new page name format program-name-program-id.

Lets just recap...

Page requested :-  abc-program.shtml

Search page shows :- abc-program-999.shtml

However it could just as easily be

free-dvd-ripper.shtml

with search page shows :-my-company-free-dvd-supreme-ripper.shtml

So I'm in a loop with google / robots.
I don't want to show a nasty 404 error page, but I need to break the cycle, so that google is updated and looses the old url.

Or do I? , it is traffic.
Maybe I'm being penalised by google?

Anyway, if I wanted to break this cycle I guess I could just add NOINDEX,FOLLOW.

Thoughts?

by JM