I know this has been covered extensively here, but I just removed 400 category pages. I removed them because I had 600 pages for 3 different products, so I downgraded to just 200 unique pages for all 3 products.
My HTACCESS file has a 404 error document specified, and I removed the 400 pages from my server so they don't serve up a 200 status.
In Google's Webmaster Tools > Diagnostic > Web Crawl, in the Not Found category it's showing about 400 or so pages as NOT Found.
Is this OK? Since I didn't restructure my site and didn't move those category pages anywhere, but just removed them and therefore potentially duplicate pages, then I wouldn't need a 301 redirect right?
The NOT FOUND status for google is normal and not penalizing?
Use 404 or 410 when that specific content no longer exists at any url, and 301 redirect when that content is available at a different url. Sounds like you did it right.
The only kind of trouble from lots of not found pages might come if your existing pages still hold links to the urls, so make sure the internal links are all fixed. Even then, I don't know about getting a true penalty -- it's just a bad quality signal to have lot of broken links. So just run a link checker across the domain to ensure that you removed all the old links.
Google will probably spider those urls for quite a while, just double checking based on their historical records. Have no concern about that.
As long as the links on the pages that still remain do not contain broken links, having a large number of URLs on your site that now return a 404 status code is not a problem in and of itself.
Google will clean their index eventually, but will show those URLs as Supplemental Results for a year. Make sure that the 404 page has clear navigation links pointing to the major sections of your site.