How can google know that you paid to be in a directory...
In some cases it can probably "guess" which is a paid directory and which isn't. Some directories have their rates on the submit page, so it is more of a no-brainer for google.
Some paid directories still have value.
Paying to be in a Chamber of Commerce directory, or better business bureau directory, or other such "trusted" directory will *probably* count in google's eyes (especially as google is looking for more branding signals from sites).
There is debate as to whether being in yahoo directory or best of the web or some of the other long established paid directories has any SEO value.
The other consideration, which some people overlook, is how that directory ranks. Some directories rank quite well on their own so paying for a listing, whether you get a link or not, may be worth the cost. IE you'd get exposure through their directory by someone finding them on the search engine and clicking through to your result.
To me there is no way for them to know that you paid for a link
There has been a lot of discussion about the different ways links are ranked and how much (if any) pagerank a link will pass. Typical factors are surrounding text, position of the link, and the size of the link. Many other considerations.
Google can easily find price pages. The structure of a paid directory since it has section which a free one doesn't have.
However I think that google devaluates only low value directories which is different from paid ones. Google (and users) doesn't likes directories with no selection which includes almost everything, those are usually paid directories since you're paying you're in. I see directories giving good boosts (in the old days), like BotW or business.com or yahoo. Just because they got a good reviewal process differntly from other directories. Actually I won't paid for any directory listing.
Its not as much a question of whether it is a paid listing or not, as much it is about the editorial value, IMHO. Why Google frowns on paid listings is because very often editorial integrity is pushed through the window when there is money involved, and you will end up with a Payday Loan link on a Health site. If a site/directory has established its editorial integrity long enough and Google recognizes it for that, Google won't have any issues if its a paid listing, IMO.
I'm with you McMohan. Google has always valued links from directories that show strong editorial integrity. This means that the fee paid does not guarantee acceptance and a listing. That is to say, you haven't paid for a link but only for the editorial assessment.
Cutts recently sent a signal that Google will be moving away from respecting article submission sites because the editorial discretion is limited. For the same reason they will move away from paid directories.
Now that Google's algo is much more sophisticated, and it has so many signals, there is so little value in paid directories.
Panda was a shot across the bow against article sites. Paid directories are only one step up in discretion, (and sometimes worse), so they are logically the next algo target.
P.S. "Good" article sites had decent pagerank and it was irrelevant with Panda.
Exactly - especially the part about not accepting every site that applies.
It's not a big challenge for Google to score a directory according to how many websites it lists that are junk according to Google's own signals. Uf that number goes above a certain threshold, I;d expect that particular directory to lose the ability to pass on PR.