If John Smith writes a guest blog for the high PR, highly relevant website ExampleSite.com (and includes an author bio/link to his site), and then someone from ExampleSite.com guest-writes a blog post for John Smith and does the same, would that be considered a link exchange? Would it be considered positive, negative or neutralized for SEO purposes? Is it always considered a "link exchange" and therefore a bad thing if two websites over the course of time end up linking to each other? (Seems likely it would happen eventually if both offer quality content about the same topic) Is there zero SEO benefit in this situation? Or worse, could it be considered a bad thing?
The scenario you are talking about is not a problem at all. Google is trying to get rid of useless link exchanges that provides little to no value to internet users. A bad link exchange would be where two webmasters simply exchange links and dont provide any content for users. However, if two webmasters with related sites work together and guest post for each other then it will not only increase backlinks and viewership, but Google will like it because you guys are creating quality content for your audience. I mean if you were running a finance blog, who wouldn't want to hear from another finance expert and some of the methods they use to build wealth? As long as you provide high quality content then this is a well-deserved backlink and should be applauded.
Yes, relevant link exchange is helpful but Google doesn't allow this, you can do this until Google notice you.
Yes, it's considered a link exchange and it's good. What Google really hates are the websites that buy links if it sees that two webmasters work together by exchanging links, that's definitely a good thing. This... There's no such thing as "Google doesn't/does allow" as far as linking is concerned, your site will just get penalized if you are doing it wrong. Google has become so strict in terms of the relevance of the links and that's the reason why Penguin was necessary. Majority of the webmasters were thinking that there's little benefits in linking out to other sites and Google wants to change that.
google was after sites using link exchange as a measure of gaining pagerank/backlinks even log before penguin update. this type of link building is not natural and the whole purpose of this method is to pass pagerank or backlinks which google can figure out very easily. i have been telling people to avoid link exchange for some time now but i still see lot of people going heavy with link exchange. here's a post i wrote about link exchange some time ago: http://blogs.digitalpoint.com/entry.php?b=54
I still do as many link exchanges as I did pre penguin. Now I am a lot more careful with anchors though and try to have brand/URL for at least 50% of the links.
Link exchange is not a good idea. Sooner or later some update like Penguin might eat up your SEO work. Better publish unique content which is unique and likely to be popular. I know it is to tough to find unique content but if you write about current developments in your niche you might find many unique and popular topics.
Natural links are pretty mutch a myth and it's very hard to scale. As long as you do the links exchanges well it will keep working good for a long long time!