For any page that issues a 404, the search engine will look for that page a number of times before stopping. If there are links to that page, the search engine will check the existence of the page again from time to time. This is perfectly normal. For all other pages, redirected or otherwise, it will take a while for any search engine to figure out what is going on.
When there are a lot of 404 or other errors, search engines will stop normal indexing, spot check the site, and if enough errors found, re-validate the sites existing URLs within the index before indexing any new pages. This is the general behavior and any existing queued fetches will continue.
The reason for this is simple. The search engine needs to ensure that the links they are making in the SERPs are valid. So, for a period, any URL that has not been validated will be pushed down in the SERPs until it is ensured to exist. All of this takes a while. Search disruptions of this type are perfectly normal. It is not a penalty. Search traffic will resume once the search engines have validated your URLs.
Your job at this point is exactly what you seem to be doing now. Ensure that proper 301 redirects exist and that the target page is appropriate based upon the topic. For any page that does not exist or where a 301 redirect is not appropriate, a 404 is the easiest route. While a 410 Gone error is faster and will reduce the 404 errors, it is not as easy to implement. What is important to know is this. Do not mark any 404 error for a non-existing page as being fixed. This tells Google that the page should exist and the process starts over again. 404 errors, if correctly issued, should be left alone and allowed to process naturally.