I would just link exchange with people you have know here (or elsewhere) for a while so that you don't have to keep checking the other sites to make sure that your links are still there. Link exchanging works beautifully if those links will be there for the LONG RUN, and the other are also right - make sure the websites you are exchanging with are of equal or higher PR. Every little bit helps in terms of backlinking.
If everyone did that, there would not be too many of them Ignore rank, go for traffic and relevance. Quality has to count for something, and a well placed PR3 link is better then a poorly placed PR5...
Make sure the link page looks like a natural links page, something that visitors may find interesting. A link page that's clearly for link exchanges will just hurt your site.