Seopti for the first case "The first and worst case is when you don't appear #1
when searching for your domain name." I would say its more one of those minus penalties and they should be automatic. If you fix the issues, your rankings will come back after 30 days.
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]