In my experience as soon as you mention nofollow you never hear from them again unless it's to persuade you to accept the dofollow link. They are already aware of google's guidelines but are hoping you are not.
Here;s what google has to say on paid links.
Paid links: A site's ranking in Google search results is partly based on analysis of those sites that link to it. In order to prevent paid links from influencing search results and negatively impacting users, we urge webmasters use nofollow on such links. Search engine guidelines require machine-readable disclosure of paid links in the same way that consumers online and offline appreciate disclosure of paid relationships (for example, a full-page newspaper ad may be headed by the word "Advertisement"). More information on Google's stance on paid links.
The full article can be found here -https://support.google.com/webmasters/answer/96569?hl=en
The link for more info goes to this page https://support.google.com/webmasters/answer/66356?hl=en&visit_id=1-636513813229010538-2003718437&rd=1
If any site truly wants to pay to advertise on your site, rather than getting 'link juice' they will not object to a nofollow link.
I hope that helps,