After cleaning up the mess I had made (what caused my initial problems with Google - I believe, anyway - was that I changed domain names without setting up a 301 on the old one), I submitted a reinclusion request about a couple of months ago.
I got the standard automated responses after firing off a couple of emails to Google. I didn't believe anything would ever come of it, and had all but given up hope. Then, a little over a week ago, Google started hitting my site hard and heavy. Basically the whole site was crawled and indexed within a few short days where G's spider had been absent for months.
I'm really not sure if it was my actual reinclusion request that brought Google back. Googleguy had said in post around here somewhere that thousands of websites had been reincluded with the recent update, and it was about that time that my site started getting crawled again.
But with all the pages showing as supplemental results except a couple, I'm still not entirely sure if I'm 100% back in Google's good graces.