Sebastian has posted a good interview with the Sitemaps team. The most useful tidbit (which I didn’t know until now) is that Google treats a 404 HTTP status code (page not found, but it may reappear) and a 410 HTTP status code (page not found, and it’s gone forever) in the same way. I believe that we treat 404s as if they were 410s; once Googlebot has seen a 404 at that location, I think we assume that the document is gone forever. Given how many people use 404 instead of 410, that’s probably a good call for the time being.
Most of the interview is not about HTTP status codes though, I promise. The only thing I’d change (we’ll see if Sebastian reads this) is to make the questions a different color from the answers so it’s easier to browse.