301 to the category page seems good. You should definitely setup a 404 page too. The more specific the redirect, the better. Right now, the way the 404 redirect plugin for Wordpress works, it doesn't show up as a 404 anymore. Basically it's going to return a 200 response, no matter what was requested. But it's still better that you fix as many pages as possible, so it won't look like your 404 page is duplicate content.
Without a doubt 404 errors will hurt your rankings. Google does not like to include sides that are 'broken'. Remember they want to give users a positive, good experience and a site that has many 404 pages is obviously not going to give that. Coupled that with the fact that 404 pages indicate a badly run and possibly outdated site. 301 redirects are very important to replace the 404's.
Great Post and Thumb Up! I totally agree with you. In our shop 404 are on the rule because items get discontinued or moved into other categories and I do not always find the time to write 100's of 301 redirects. Yes, it might be annoying for the user to come to a page that ends up to be a 404 but it it does not hurt any rankings, neither PR nor SERP. Especially e-commerce sites do have the 404 problem unless you really have time enough to always link to a similar product, if available or to the accordingly correct category if the product was moved. I can confirm google will take those pages out of their index and since caffein even a bit sooner than before. Yahoo isn't that fast but offers in their webmaster tools also a tool that allows you to delete those pages from their index, very similar to google's webmaster tools.
well, there were many pros can cons, does google hurt or not your ranking if you have to many 404s. I have many products in the e commerce store, and time to time i have to delete disco products and add new once, Since last big deletion in march, i did get hurt by google crawling , my rate become very low. i have about 70-200 404s all the time. So, i just have to think, should i just not to delete any url, and just store them and hide from the customer. for me questions about 404s still not clear