@McMohan: regarding the cleaning process: yes, all of what you said, compounded by the fact that the supposedly bad links are normally on supposedly bad sites which may themselves be already banned or severely penalized hence no allotted crawl budget to speak of. It may take AGES for Google to re-read 100,000+ of pages of a site that only has 1000/day crawl budget (or less). In case your worst links wound up on a very bad site that got completely banned, I can tell from experience that crawling of banned sites eventually stops altogether. THEN how does Google knows you've removed your links?
This is a mess, a complete and utter mess Google has created themselves by their over-reliance on results of other people's work (i.e. properly, in good faith, linking relevant HTML pages). This was a system designed for failure, too bad the two geniuses Larry and Sergey could not see this coming. 15 years later, sitting on mountains of cash, they are still unable to tell what the page is ABOUT, they can only meekly try to get clues from that other people tell them through the easily abused links.