Has anyone had a similar problem and used this type of solution successfully? Anyone got any thoughts on the good / bad impact this could have of the site from a search engine perspective?
First, changing domains is one of the most destructive things you can do to a website. And doing it linked to a site you know to be penalised is, er, not wise ;)
The real issue is the damaged site. Reinclusion requests are a very dangerous thing to do unless you are completely and utterly certain that your site is as clean as a whistle. or cleaner.
Most bans - especially link farm farm bans - are algorithm bans, and will self correct a while after you correct your 'error'. If you seek reinclusion for a site, you are saying to google "LOOK AT MY SITE" - so if you've failed to clean up, an algo penalty may be lifted. And replaced with a manual penalty. Not to mention that every 'wasted' reinclusion request takes Google's resources, and they are hardly likely to thank you for requesting re-inclusion of an unclean site.
You may be right that the link-building thing brought you to google's attention - but there may have been other things that had previously been under the radar, and now have been noted.
Check the site again, and again, and then reread the guidelines and check it again. Remove ALL links that you do not 100% recommend, and know to be kosher. Remove ALL reciprocal links. Then check all remaining links and remove any that aren't "The Best". Then remove any 'paid for links' that you don't recommend.
Then xenu the site, and fix navigation errors and remove all orphan or obsolete pages.
And so on. Never assume you know the reason for a penalty; you could be wrong. Good Luck :)
