That's the problem I think is the biggest problem, I'm sure Google isn't penalizing if they aren't fully sure about the case. But I am very sure that it's possible that the wrong websites got banned too, which is a big problem for that owner.
Exactly, and even in google webmaster tool you can report any of your competitor's website "As a paid links Website" then it will be totatly on the mood of the google's employee who is going to read it at that moment and take action on it to penalize it or not, in that situation website's owner will be having some serious pain in his A**.
They should not, Publishers makes websites, and it takes money investment on domains, hosting, conetent, promotions, design etc, and some serious hard work as well. So publishers should have rigths to monitize their websites the way they want no matter if its paid advertisements or links, after all we publsihers get business for google because we make websites which google and other SE's use to show relevant results.
That is not the issue. The real issue is easily manipulating the serps with paid links.