I hear a lot about turning old 301's into 404's these days and from personal experience I have had nothing but bad results when doing this.
One client had been hit by a panda update and he insisted we do 404's to all the bad and what he thought was duplicate content. We did this and he dropped even further. 3 months late we 301'd the pages we could remember to the best fists on the site and the site recovered to traffic levels post original hit. It never recovered totally but it did at least get back some traffic.
Yes 301 redirects when done wrong can be dangerous but when done right are way better than 404 pages. Unless of course the pages are extremely spammy or spun content. However in a case like that I think your site probably will never recover.