if you deleted a page, but the page has external (or internal) links pointed to it, it will still periodically appear in WMT "Not found" error section. if external links to such page were contributing to ranking of your website, then deleting pages without redirecting them may result in ranking drop.
The best would be to redirect deleted page to either a similar page or its category page if that is at all possible, and to internally link to redirect target. If there are no external links to page you deleted, then return 410 Gone with a nice custom page so that you do not lose your visitor.
ON the other hand, if page never existed, just leave it returning 404 (as said above).