A client recently came to me for help. His site has recently got a warning from Google for having unnatural links. Obviously, his site got penalized and it bombed in the rankings for his main keywords( in an extremely competitive market) His previous SEO was using black hat methods to get links (blog comment spamming, article spinning, social bookmarking, all the sorts). I used Open Site Explorer and realized there was up to 17000 links pointing back to the site, 90% of which was to the homepage, using exact match anchor text.
-manually removing those links (extremely crazy)
-using Google disavow tool (low chance of success I presume)
-starting over with a new domain name.
I am open to suggestions about what I can do to help him. Would removing those links be a good idea, or is starting with a new domain be better? Is there anyway i can preserve the PR and good links from the previous domain?