Hi loopyal, sorry for my bad english maybe I got you confused.
I'm exactly saying what you state above, even if someone pays you in the street, google may know it's been a paid link, but not because they got a radar on all of us but just because you've replicated a process which get your content recognizedas a paid link.
You're doing great on studying about who're you're linking because bad neighbours which are linking you may create or not issues but surely if you're linking to a low quality site this will give you problems.
About the site you're speaking, what I recommend is to create a valuable post for your users. If that site is in your nihce and you think they may give a valuable service to your users why not writing about them? And if you get paid is better. But beware I'm not encouraging on having content from them and publish it, but evaluate their product, ask for free accesses, make a REAL review. In that sense this review will be helpful focusing on your users and their interests. They're your "clients" and you have to always think about them, sorry if I got misunderstood I'm not saying it's easy, but just that sometimes we complicate the picture asking on how google can recognize a paid link, because they don't; they just recognize the apparel of that link which is following the same structure of paid ones, so even if it's not paid you may be penalized too.
In short. If the site writing you is a good site, with a good product, offers you to use their product, write a content about them and link to them if you find their product useful, I don't think it would be a bad thing linking to them. Just try to have the possibility of writing about their service in the most free way.