1script - 8:32 pm on Jun 13, 2012 (gmt 0)

Although my personal experience with URL changes and page removals comes from my attempts to remove a harsh manual penalty and AFAIK not directly related to Penguin (and predates it by a month or so), I would have to say that nothing short of actually removing the bad links from the OTHER sites works if you want to remove the effects of bad links on your site.

I have tried both approaches you suggests - remove the link target completely (I used 410 instead of 404) or redirect it elsewhere. Nothing worked until I by sheer chance was able to get in touch with the owner of a site that had something like 10K of my links in the WP theme he used (I sponsored the theme, hence the links) and he removed the links. Additionally, again by sheer chance, an abandoned spammy autoblog using the same theme with my links thus creating something like 7K more bad links had its domain name expired. So, I was able to lose 17K of bad links in one week and that's only when the G traffic had picked up a little.

What I think is happening is that if the link is still up, it passes some sort of a "juice" (for lack of a better term) to your site even if the destination page on your site has been removed or redirected. In other words, that link's vote for the page most likely does not count (and is meaningless anyway) but its vote for the site overall somehow still does.

My takeaway from this was: Google would not take anything other than complete removal of the bad link for a remedy to that link's negative effect on your site. It's crazy difficult to remove links from sites you don't control hence not many people can report escaping Penguin.

It's also why negative SEO works: bad links are easy to setup, impossible to get rid of.