Returning a code other than 404 or 410 for a non-existent page (or redirecting users to another page, such as the homepage, instead of returning a 404) can be problematic. Such pages are called soft 404s, and can be confusing to both users and search engines.
A soft 404 is when a web server returns a response code other than 404 (or 410) for a URL that doesn't exist. A common example is when a site owner wants to return a pretty 404 page with helpful information for his users, and thinks that in order to serve content to users he has to return a 200 response code. Not so! You can return a 404 response code while serving whatever content you want. Another example is when a site redirects any unknown URLs to their homepage instead of returning 404s. Both of these cases can have negative effects on our understanding and indexing of your site, so we recommend making sure your server returns the proper response codes for nonexistent content.
now look at what you call "a smart targeted 301 page redirect".
old listings are removed ... We simply do a 301 redirect to the corresponding city's home page ... lot of categories too become redundant and they are removed, so we ... 301 redirect ... either one level up/two level up/three level up/ or if none exist, then redirect to the home page.
all this sounds like perfect descriptions of soft 404 techniques.
What do you think should be done? Should we treat them as 404 or continue with the existing settings?
you could show the same content you show with the redirected urls but use a 404/410 response instead of redirecting to those urls.
What would be the impact on Google rankings when it suddenly starts finding a huge number of 404 errors.
from the first WMT Help link above:
Generally, 404 errors don't impact your site's ranking in Google, and you can safely ignore them.
the fact they are reported doesn't make them a problem but if you see something reported that looks like a problem you should address it since that might impact your rankings.
and from the "Do 404s hurt...?" blog post:
Q: Do the 404 errors reported in Webmaster Tools affect my site’s ranking? A: 404s are a perfectly normal part of the web; the Internet is always changing, new content is born, old content dies, and when it dies it (ideally) returns a 404 HTTP response code. Search engines are aware of this; we have 404 errors on our own sites, as you can see above, and we find them all over the web. In fact, we actually prefer that, when you get rid of a page on your site, you make sure that it returns a proper 404 or 410 response code (rather than a “soft 404”). Keep in mind that in order for our crawler to see the HTTP response code of a URL, it has to be able to crawl that URL—if the URL is blocked by your robots.txt file we won’t be able to crawl it and see its response code. The fact that some URLs on your site no longer exist / return 404s does not affect how your site’s other URLs (the ones that return 200 (Successful)) perform in our search results.
We could also add the "Google Webmaster Tools 404 widget " to the 404 page which would show relevant related pages...
you should do your own work there and create a better custom error page.