Defining a paid link can be difficult. A directory listing in Yahoo could be called a paid link (whereas it is a paid review for a site) but is usually beneficial. A paid link on a page which is nothing but paid links would obviously be bad. The fact is that search engines have detected sites which are primarily making money out of selling links from their pages and have penalised both them and the sites they link to. Using commonsense is what I always recommend.
I would bet that a lot of site owners, and even some big corporations, have bought links without being penelized by Google. In fact if you pay someone to do link-building for your site, or even spend time doing it yourself, you are essentially buying links.
It's impossible for Google to strictly enforce this rule, since a competitor could buy links for your site as a way to try to get you penelized.
The search engine doesn't penalize web page's that it detects have links appearing on all the kinds of link building schemes, whether paid for or artificially manipulated (whether the link be dropped on a blog comment, dumped into a garbage directory, swapped for with your competitor's as a friendly link?, solicited, tricked into, coerced, triangulated, wheeled out by the PR pint full etc . etc. etc . it simply assigns little or no value to those off-site ranking influences.