Googleでは明示的に、いわゆる「有料リンク」をかたく禁止しています。
詳細はGoogleのガイドライン
http://www.google.com/support/webmasters/bin/answer.py?hl=jp&answer=66736
に記載されています。
これによると、
・検索結果の操作を目的としたリンクの売買を禁止
・広告リンクの場合、広告であることを明示する必要がある
と記述されています。
PRを目的としたリンク広告の売買は経済活動として認められていると記述されています。しかし、通常のリンクの形態を偽装したような有料リンクに関しては一切認めない、という態度をGoogleは一貫しています。
Googleがそういったガイドラインを遵守する姿勢を広くアピールする結果となったできごとが、Google Japan（Googleの日本法人）へのペナルティです。
2009年2月、Google JapanがPayPerPost（ペイパーポスト）と呼ばれる、お金を支払った見返りとしてブログ記事を書かせるブログマーケティングを利用したことが発覚しました。
Google
Japanは公式ブログにて、この事実を公表し、この行為自体がGoogleガイドライン違反であることを認めました。（http://googlejapan.blogspot.com/2009/02/google.html）
これに対し、アメリカのGoogle本社はGoogle Japanのサイト（http://www.google.co.jp/)のPageRankを8から5へ下げました。（2009年12月、PageRankが5から8へ戻ったため、ペナルティは解除された模様です）
明示的に公表はされていませんが、Googleガイドライン違反へのペナルティであることは間違いありません。
皮肉なことではありますが、自社内のサイトを処罰することで、Googleの有料リンクに対する姿勢が改めて広く知られる結果となりました。
このように、有料リンクが発覚した場合、大きなペナルティが課せられることが予測されます。
Google
Japanの場合には、たしかに大きなペナルティではありましたが、もともとの事業規模が大きく知名度も高いため、大きな影響はなかったことと思われます。
しかし、中小企業や個人経営の場合には致命傷になりかねません。
また、有料リンクのペナルティというと、購入した側のペナルティが多く話題に上りがちですが、Google Japanの事例でも分かる通り、有料リンクを販売した側にもペナルティが課せられます。
以上のことから、SEO目的での有料リンク売買にはうかつに手を出さない方が良いでしょう。