SevenCubed - 11:05 pm on Oct 27, 2013 (gmt 0)
...and opting for 404 over 301 even though they had no logical place to go.
I got my hands on a site this past June that had tanked in google and was thrown out of Bing/Yahoo. It had existed for 10 years prior and had gone through numerous redesigns along the way (verified in The Way Back Machine).
The main problems were immediately obvious. It had so many orphaned pages, broken links, as well as having been hacked (an unused old WordPress installation with default everything left in the root).
It's just a small site for a local business. It had just over 100 pages in the web space when I took it on. After redesigning it and cleaning it up I got it down to about 25 pages.
It took a few months but it has come back in top results for targetted terms in google and Bing/Yahoo has them back in favour on about top page #2 for many terms, page #1 for others.
I didn't let anything return 404. What I couldn't 301 I 410'd. I can't say that's what helped but it probably didn't hurt. 404 is a default reaction to a missing page. It could be missing for many reasons including webmaster error. But a 410 is explicit, it requires manual action to make it happen. For me, if I were a search engine engineer, I would treat that as a website with "awareness" and under someone's careful control.
I don't know if search engines pay special attention to 410's or not but if they don't they should.