Search Engine Roundtable reports that there has been a documented case of a site being banned from search engine results because of using a link exchange.
The search engine in question was Live Search (the artist formerly known as MSN search.) The email from the MSN Spam Team (as republished from Search Engine Watch forums) goes:
Your site is acquiring links through posting to or exchanging links
with sites unrelated to your site content. Techniques which attempt to
acquire unrelated spam links in order to increase ranking are
considered spam and your site has been excluded from our index as
results. Please contact us once you’ve removed these links and we will
SE Roundtable goes on to say that they believe Google doesn’t ban sites for using link exchanges, but that unrelated links to your site are just not counted.
The bottom line: find relevant incoming links to your site and don’t bother with link exchanges.