As far as I'm concerned google penalizes for backlinks you buy on other websites. But links exchanges are allowed. How does google know what is a link exchange and what is a backlink I bought for money? Will I be penalized if I do about 500 three-way link exchanges to a single page?
Google mostly penalizes sites that sell links. For those that buy links, the links can be devalued. In extreme cases, Google may devalue a majority of a site's backlink profile for buying links. It's all about trust. If Google does not trust your site, they will spank it. Google can tell its a link exchange if both sites link to each other. That's easy enough for them. Paid links that are stuffed in the footer, or in other link clusters, along with unrelated sites are easy to determine. It's much harder for Google to determine if the links are from highly related sites. In time, you most likely would be penalized. Matt Cutts has said their algorithm can detect most 3-way link schemes. Reciprocal links do not carry much seo weight. If you must exchange links, do so when the opportunity exists to gain relevant traffic. For SEO purposes, focus on quality one way links pointing to your site.
IMO, it's all about two things: 1. the suspicious things you done, like link spam etc. is parameter A 2. how big you site are, the reputation of your site. is parameter B Google penalize a site if A>B*C%, C is a percentage of unknown It's explained why so many porn links to Disney and Disney OK, it's also explained why it's very hard to frame a big site but easy to a small one.
If it's a link exchange it can easily be determined because both sites were pointing to each other. If it's a paid link, it's only 1 way and google can easily find out whether it's paid because most of the time the links are non-related to your niche. Another, never also engage in open dealings when buying or selling links. A simple search using their own google SE will come up with tons of results. If you do 500 three-way link exchanges to a single pagealone, that is spamming and will get your site penalized.