Originally Posted by inertia

Ive seen this happen with sites that have used spammy techniques in the past. We had a client whose site arrived with us in the same condition as yours. After trying lots of different techniques (content change, reinclusion requests, links building) we made the decision to start from scratch with a new domain name. 9 months later and (after a period of sand box) the site is doing great.

I understand that Google "doesn't hold grudges" but i am tempted to disagree. Anyone agree?