Days, Weeks and Months...
It can take Google days, weeks and even months for Google to remove pages marked noindex, robots and 404's. Generally it takes Google several crawls before Google acts on the new information of a page.
It should be also noted that more than often users make human errors and create 404's, noindexs and so forth by error, simply removing the pages straight away would cause harm in rankings to such little mistakes, so It's my belief Google does this on purpose to ensure that these are intended changes.
Web Master Tools
Over the years many webmasters have said exactly the same as you over and over, and more times than I can count. Google made changes to Webmaster Tools several years ago allowing webmasters to quickly remove a URL by making a request. If you have a few pages that you want removed straight away then you should make a request, this is by far the quickest method and you should ensure that the pages return noindex if the page exists or a 410 gone to prevent it being re-indexed or denied removal.
410 vs 404
While a 404 is perfectly normal on a small scale it should be noted that 410 is actually preferred, this tells Google the page is GONE FOREVER! while a 404 could be used temporary, or if you have just a few pages that your not fussed about.