jimbeetle - 3:41 pm on Jan 10, 2013 (gmt 0)

Do not do a link exchange! Google flat out bans them in their SEO guidelines

No it doesn't. It mentions that "Excessive link exchanging" can negatively impact a site's ranking in search results. And Google can't flat out ban anything.

A well thought out exchange such as above is perfectly fine.

For instance, a pet store and a dog walker have a real reason to link to each other (same target audience, relevant products/services).

And why would this not be a link exchange?