pageoneresults - 5:41 pm on Jul 31, 2010 (gmt 0)
I have personally experienced a degradation in rankings due to a 404 mishap. The site has approximately 1,000 documents. After launching a new application, we discovered a bug in the rewrite that caused Googlebot to index 1,000+ documents that were returning a 404. Unfortunately we did not catch this in a timely manner and sure enough, not long after, we started to lose organic traffic.
Since we are in a very controlled environment, we were able to determine that the loss in organic traffic was a direct result of the 404 issues. After correcting the rewrite, traffic returned to normal within 30 days and actually improved a little thereafter.
Note: These were internal links returning a 404.