Until I get my notes sorted from the WMW conference, I thought I would share some info on how to do a reinclusion requestion to Google. This is only for sites that are not indexed at all. In other words, if you do a site:www.yourdomain.com command, and no information is returned, then you are not indexed. Assuming your site is clean (follows Google guidelines), you can politely ask Google to consider reincluding your site in the index. If, for instance, you had been banned for using shady techniques, you could clean up the site, and ask to be reincluded. Or perhaps you bought a domain that got banned because of the previous owner's misdeeds, then this would be another reason to use this. Note: Make sure your site is clean (white-hat) and spam free before doing this.
To submit the request, go to www.google.com/support and answer the first couple of questions. When you get to the form, type in "reinclusion request" in the Subject field. Then, explain your situation (politely) in the description area. Make sure to mention that you ran the site: command and that you are not in the index at all. After submission, you will receive an autoresponder form email which simply states that they received your request, and then it lists all the possible things you can do to be included. Most likely, you already know all of this, but I suppose it can be useful for newbies.
If you ever need to contact them again about the same situation, be sure to reply to the email you received as it contains the trouble ticket number. Now all you can do is sit back and be patient. Whatever you do, do not get snippy with them. That will only make things worse.