SEO and 404 error redirection

Question

Recently I've removed some products and categories from my Magento store and that generated many 404 errors as the pages wherein the research index and now they don't exist anymore.
I was thinking about developing/using a module that takes the request to the store when they should give 404 and use keywords from the request URL to build a search query on the website so the customers don't get stopped by a dead link.
But the question is: will that kill my SEO? How does Google, for instance, couple with the 404 error suppression? As anyone else encountered this problem and tried something like this?
Since the operation will take quite some time, I would like some feedback before going into this road.
As of now, I only know that redirecting 404 errors to the homepage or another page is bad as it keeps dead links alive, but redirecting with criteria will have the same "zombifing" effect?