We had our pages automated to 301 when we deleted pages.
301 to where? The front page? Google calls that a "soft 404" and they absolutely hate them.
That being said... wmt lists all the 404s and 410s that they ever find. It doesn't necessarily mean you did anything wrong. "Yes, thank you, I know it's gone, I deleted it myself." It's just for your information.
we now designed 404 unique page that shows users site map search box and links to main site.