crobb305 - 12:32 am on Jun 8, 2012 (gmt 0)
I'd personally get rid of the links as quickly as possible. Consider the rapid recovery of WPMU. I've contacted dozens of webmasters, had over 100k links (mostly large-scale sitewides) removed, and I have not dropped further in ranking. Additionally, I still rank very well in Bing. The bad links were probably already discounted, and had also led to a more aggressive penalty (where I don't even rank for snippets of my own content and position 3 or higher for my domain name).
My gut feeling is the faster we distance ourselves from bad links (whether they were solicited or unsolicited), the faster Google will forgive. Google is also taking a considerable amount of time to discover removed backlinks, so it isn't an instant process. Over half of the links that I had removed 4+ weeks ago are still showing in WMT and cached. Follow your gut instinct. Don't rely too heavily on the advice of someone who is profiting from you.