Hi Peter,
It is widely known now that any kind of compensation given for a link is against Google TOS (that includes affiliate links, "powered by" links, PRs, sponsored posts, etc). All of them should be not followed, in that way, you still get the people that may want the services you offer without affecting Google rankings.
There are some rel alternatives that could help Google recognize those links and not count them towards your rankings (or counting them differently). Take the case of Wordpress, most of their hosted blogs have a "powered by" link, but they use rel="generator" which helps Google distinguish between spam and "powered by" links.
Anyway, there are 2 sides of the coin here. Google said that affiliate links should be nofollow, but I still see sites that have hundreds of thousands of links (over 95% of their link profile) from affiliates, which are followed and not blocked by anything and the site ranks 1st.
I would recommend to nofollow those links, but that is my approach. I even created a javascript method to insert our affiliate links (including the nofollow tag), still, we are ranked 10th on the same query that the site I mentioned above ranks 1st.
Hope this answer helps you at least decide what is your approach and what to do...