dougwilson - 10:02 pm on May 29, 2013 (gmt 0)
"... the problem and all we could find were the paid links"
"... all the links we are paid to have on the site are nofollowed"
I'm missing something here. What links did you, are you, buying? That is, as far as I know, what is referred to as paid, or buying, links.
Ads, adsense, affiliate links etc are common practice.
I'd use something like Link Slueth and find every link on your site, then check them out. Is this a blog platform website? Check code for injected links.