Link exchange is still valid and works (in part) for increasing rankings in search engines by increasing link popularity. It's considered "white hat" if you do it right.
Obviously there are other factors (over 200 metrics according to one of Google's patents) that affect rankings. Linking is not the only factor that affects your rankings. It is only part of the equation so make sure your content is rich, updated regularly, and useful for the internet.
It's important to make sure if you obtain links through reciprocation that you do it slowly and naturally with high quality sites relevant to your own. Don't link in high volume with low quality sites that are unrelated to your site.
The search engines have never said "do not link exchange". They have only warned us to avoid high volume irrelevant linking because link exchange has been abused in the past just like paid links and other methods for obtaining links.
An easy way to get relevant links to your site is to put some verbiage off in a corner of your homepage that reads:
We are always looking for relevant links from high quality sites in the keyword, keyword, and keyword related market segments. Click here to suggest your link (insert your industry keywords).
and then hyperlink the verbiage to a form or method of contact. Some websites will publish graphics and methods to link back to the site. You will be surprised how many sites will link to yours in anticipation of a linkback.
Of course you should always maintain editorial discretion and only link to sites that you deem are useful for your end users to visit.
Remember linking with other sites is not only an SEO function. Relevant link exchange is first and foremost a branding and traffic building function. It's an SEO function as a by product of linking. Don't make linking decisions on how you think its going to affect search engines.
Link exchange still works. Some here will disagree with me maybe because they do not have the patience for the time it takes, or they dont know what software and methods can be used to speed up the process. I have been building links for client sites with relevant link exchange for 11 years. You can get a brand new site to rank well after a month or so with just a handful of high quality relevant link exchanges. The key here is quality not quantity.