Bad History Timeframe

[gulfshoresbum]

I am working with a site that has quite a bit of bad history. The site was kicked out of DMOZ back in '99. Hence it was kicked out of any results that matter for Google. We've recently done a redesign of the site to get all of the spam off of the site. The site has lots of old incoming 1 way links.

I want to know if there is any way to get back into the good graces of these entities. Has anyone had similar experiences and gotten back into the organic SERPS? Should we just cut our losses and move on?

Thanks