Well, you can have a lot of discussions also on what is the definition of payment.
If you compensate an incoming link with an outgoing link from your sites, isn't it a way to pay (reward) a service?
Or by payment they intend "brutal reward in good currency"?
There are many way to reward a favour (i.e. an incoming link).
If there is a link on the official website of an Embassy of my Government, and that link is directed towards a business competing with me on the market (a profit institution) and this cannot be hosted there, can I report this as "paid this with bribes as Embassies should not supposed to host links to commercial sites or else, to host links to all the commercial entities of that industry?"
Also: excluding the obvious cases of websites set up for the unique purposes of selling links (come on you cannot ask the name of them to me, there are a lot of sites like this and their names are public) how do you discover a paid link if not via an investigation of the "contract" which might well be hidden or not published, or not public or simply not said?
In any case, there should be a "trial" for every case as my sites that have thousands of spontaneous incoming links cannot be penalized, not even for one or two only links, simply because an evil competitor will like to damage my business and Google will have to automatically believe their declarations.
"Hei, GiulioRapetti's website is benefiting from paid links: he's linked from the site Widgets.com and he paid 300 euros for this!"
Ok, what can Google do in this case if not asking Widgets.com's owners?
Unless Widgets.com's site has a clear public policy on their pages stating "you can publish a link on my site by paying me #*$! euros/dollars" of course Mr. Widgets.com's sitre owner will reply to Google "no no I'm not doing this"... as he/she will have all the interest in protecting this "now illegal" source of revenues...
As I can't believe that Google will blindly believe anyone's statement , there will have to be a very deep and difficult investigation behind it. Which is somethign that will make sense (in terms of time spent) only if we are talking about big and a few sites.
If this is an activity to be done on tens of thousands of cases, I think that we, honest spontaneous linked sites, are all in danger or at least exposed to sabotage...