A Google Webmaster Help thread has a comment from a Googler that implies Google may be speeding up the process of re-including pages that were removed from Google index by accident.
A Webmaster accidentally 404'ed a page on their site, which obviously resulted in Google removing the page from their index. As soon as they figured out the mistake, the webmaster removed the 404, but by then it was too late and the page was gone. This page was a very valuable page to the site owner, being 10 years old with many quality links. But now it was if it never existed.
New Googler, Pierre Far, said:
This specific issue should fix itself in the near future, but we are looking at ways to have such issues recover sooner.
This implies that Google is looking for ways to return 404ed pages that remove the 404 HTTP header status quicker than they have in the past.
I assume that means Google will either add a tool to Google Webmaster Tools to enable people to notify Google of these mistakes, like they have for the page removal tool OR GoogleBot will fetch 404 pages more often.
Forum discussion at Google Webmaster Help.