The 404 message isnt really stating that the page has been removed, it can be a temporary 'page not found' so the engines are going to keep coming back for an update.

The 410 however is telling the engines the page has been removed forever so stop wasting time coming back - but its a bit strange that Google sees a 410 as 404, I would say thats Google just being stubborn as not to remove data from their index.

Google hate to remove information from their index and it would "seem" this could be the main reason why old urls are still being listed.

__________________