It is confirmed that Google may penalize your website rankings in organic search if you are selling paid links (like Text Link Ads), writing sponsored posts or participating in link exchange schemes. These things can also have a negative effect on the overall Google Page Rank of your website.
Now if your website is penalized by Google for any of the above reasons, the best approach is to remove the text links (or nofollow them) and submit a reconsideration request from the Google Webmaster console explaining the exact changes you made for Google to remove the penalty.
This approach works most of the time and your Google referral traffic will return to normal levels within weeks of submitting the reconsideration request.
But what you do in the extreme case when the Google penalty persists even after cleaning up the site ?
Matt personally looked at Donna’s site and found that the footer was a problem as it said – "This blog accepts forms of cash advertising, sponsorship, paid insertions or other forms of compensation. The compensation received may influence the advertising content, topics or posts made in this blog."
The other issue, as Matt shared, was a previous post on Donna’s site that was a "sponsored article" but without rel=nofollow and hence violating the Google Webmaster guidelines.
Now that she has changed the footer and nofollowed all the sponsored links, Matt says the issue could be resolved in the next few days. Awesome.
Long story short: If your website or blog is penalized by Google and you are planning to file a reconsideration request, make sure you have completely cleaned up your website. The penalty is likely to stay even if you a single paid link on any of your web pages.