1script - 4:13 pm on Sep 1, 2010 (gmt 0)
I was able to "clean" a formerly parked domain name by filing a re-inclusion request. It was rather quick, too. Within a month or so it started behaving normally - normal G*bot visit rate, PR growth, # of indexed pages etc. I should mention though that I was not the one who parked it, the previous owner did and so I stressed in the request that I just bought it and I'm using it differently from the previous owner. Maybe ownership change has helped. If you feel like you've exhausted other options, maybe you can do some creative inter-registrar domain transfer (without contact details) and then file the re-inclusion?