How to de-index URLS that already return 404?

[realmaverick]

I've been battling now for 6 months with Google, to remove some URL's from the index.

The page returns a 404, the meta is set to noindex and NOWHERE on the ENTIRE website links to it. Nor externally.

WMT keeps reporting the page as "404 not found". Well that's because it's been deleted.

What else can I do, to remove these URLs? They're plaguing my WMT and make it difficult to spot actual issues.

[tedster]

Are they only showing up in WMT, or are they also showing up in search results?

<added>
The reason I ask is that URLs are only in the active index if they show up in search results somewhere. In WMT, there should be information in a link to the right about where googlebot is still seeing links to those 404 URLs. Recently WMT seems to have run amok again for some accounts, but at least that's the way it's supposed to be.

The page returns a 404, the meta is set to noindex

If a URL returns a 404 response in the HTTP header, then meta information does not enter into it. Is there a chance that you are serving up a "404 error page" but not returning a 404 status in the http header for the original URL request?

[realmaverick]

The reason I ask is that URLs are only in the active index if they show up in search results somewhere. In WMT, there should be information in a link to the right about where googlebot is still seeing links to those 404 URLs. Recently WMT seems to have run amok again for some accounts, but at least that's the way it's supposed to be.

Most are not in the index. One of the 404's was recorded yesterday, detected: Apr 16, 2011. It lists 2 pages linking to it. Which were sub pages of this page, that are also gone. The discovery date is Oct 18, 2010.

I don't know whether now that it's detected it's missing, it may eventually remove it? I'm just frustrated by tons of needless rubbish in WMT, that makes detecting issues difficult.

[Planet13]

Is it possible to do return a 410 instead of a 404? I remember Matt Cutts saying that it can be quicker.