g1smd - 2:55 pm on Jun 27, 2011 (gmt 0)
There is a lag between what they crawl and what they remove from SERPs.
They need to be sure that the 404 isn't just a temporary glitch on your site; using 410 might be better.
Sitemap files must include ONLY valid URLs. Don't link to non-valid URLs from your sitemap.