Last I tried google wouldn't remove 'deleted' pages from the index because they still 'existed'. :(
That's a good point. Why doesn't MediaWiki return a 404 when a page isn't found? As far as I know, we could show exactly the same page, it's just a matter of changing the status header from 200 to 404. Same applies to redirects - HTTP has a "Page Moved" code, or something similar, which we should return.