Welcome to WebmasterWorld Guest from 126.96.36.199
Also, it sometimes seems possible to get a speedier removal of a penalty with a reconsideration request, even though an algorithmic recovery "might" also have happened eventually. At least there are reports of rapid lifting of a penalty within days of filing a request. Other reports are around of a 90 day wait in some cases, with or without the request.
If the concern is trying to clean up an area that tripped a penalty without having other borderline practices scrutinized by human eyes -- well, I don't play in those waters.
The underlying assumption in this question is that we know "which penalty" a site suffers from. Except for the extreme kinds of evidence that the opening post mentions, we often don't.
In fact, many ranking drops are NOT any kind of penalty at all - there's no "flag" against your domain or your page for anyone to lift manually. For example, most duplicate problems fall into this area. If you fix the issues involved, then rankings can almost magically be seen again. That's because your site threw an indexing problem at Google and then you fixed it. There never was a penalty.
It works like this: If you get penalized, Google will revisit the site 30 days later, and if you got already rid of the issues, you will be re-included automatically. No re-inclusion request is required.
About the "Second case if your site has banned completely and can't be found with a 'site:' command."
If that happens, the best way to get back in the index is to fix the issues, make sure that you site is verified by Google with their webmaster tool, then submit in their tool an xml sitemap too, but including dates, and upon that a re-inclusion request.
Then you should sit back, have a beer and some popcorn, and watch the show. :)
[edited by: Webnauts at 1:14 am (utc) on Oct. 7, 2008]