I'd say look for important backlinks that point to problematic pages and create appropriate content at the same URL - even if it's just an explanation about the change to the website.
Just to clarify do you recommend to return a 200 OK for URLs you don't want to handle instead of a 301? Because I find it more deceptive than a standard 301.
Technically you would think a 301 will force the spider to update its index with the target URL asap. And as you know what is happening is an old or even non-existent link is accessed indefinitely. All it takes is another site that posts a link to your site.
So if I assume the spider doesn't keep a record of invalid URLs, something I find logical, it keeps accessing the same URL cause it is listed someplace else, even outside the domain. And that's the problem I believe.
Instead, the spiders should only access, list and update URLs in their index, found inside the domain and nothing else. In other words URLs starting from the root of the domain. This may be happening to an extend with their index but not with the access or update.