I was contacted by a webmaster today and their request was to remove their links from my website because they were paid links. The thing is I had removed these links a long time ago. I had a around 2-3 paid links on my homepage back in 2008 and a year or two later I took them down. My question is, is it possible Google to put a penalty on a website because of paid links that appeared a few years ago even though these links may now only appear in the chached version somewhere on the internet?
Yes I can see it happening but not exactly what you are thinking.
Imagine getting a DMOZ listing with an exact anchor text match. Let's also say you have very few links. DMOZ clones can result in hundreds of sites using that same exact anchor text which could move your anchor text percentage outside of your comfort zone.