How are you guys dealing with this? Are you setting every page to have a Follow, and all the text links you guys might buy, now you must check that their being followed.
As far as I do things, I don't add a no_follow tag. And if I see someone that I've purchased a link from doing that, I would definitely complain (and not do business with that person/site again if they didn't comply).