Google employs thousands of engineers with degrees and Phd's. I'm pretty sure they can figure out a bunch of external links in the sidebar are likely to be paid.
Google just seems to penalise PR for the sites, but it doesnt affect your PR within Google. So why not try to make some money while you can!
I think google can spot the pattern from these major link sellers, I mean some of them are no evne trying to hide the sellers WTF?
I don't know if they are banned. But my business with them was very nice. Wonderful customer service. I recommend them highly.