ergophobe - 6:08 pm on Feb 7, 2013 (gmt 0)

Paul, it will depend on how often your site gets crawled, what response code you are sending and perhaps what expires headers you send on your content.

When you remove a page, what response code are you sending? Remember

404 = page gone, maybe temporarily due to server problems or who knows what. Google needs to see a 404 many times before it removes the page

410 = page permanently removed. Google only needs to see this once I think (it will keep crawling the URL, but should remove the page from the index).

You can sort of think of 404/410 as equivalent to 302/301 for redirects in some vague sense.