Which methods do Google (and other PPC companies) use to prevent click fraud?
Here's What Google Does: http://googleblog.blogspot.com/2008/03/using-data-to-help-prevent-fraud.html
Google Adwords Official Answer: https://adwords.google.com/support/aw/bin/answer.py?hl=en-uk&topic=10625&answer=6114
Other Methods: There are many such as:
1) If there are multiple requests from the same IP.
2) Forensic analysis of advertisers' web server log files:
This analysis of the advertiser's web server data requires an in-depth look at the source and behavior of the traffic. As industry standard log files are used for the analysis, the data is verifiable by advertising networks. The problem with this approach is that it relies on the honesty of the middlemen in identifying fraud.
3) Third-party corroboration:
Third parties offer web-based solutions that might involve placement of single-pixel images or Javascript on the advertiser's web pages and suitable tagging of the ads. The visitor may be presented with a cookie. Visitor information is then collected in a third-party data store and made available for download. The better offerings make it easy to highlight suspicious clicks, and they show the reasons for such a conclusion. Since an advertiser's log files can be tampered with, their accompaniment with corroborating data from a third party forms a more convincing body of evidence to present to the advertising network. However, the problem with third-party solutions is that such solutions see only part of the traffic of the entire network. Hence, they can be less likely to identify patterns that span several advertisers. In addition, due to the limited amount of traffic they receive when compared to middlemen, they can be overly or less aggressive when judging traffic to be fraud.
4) Then, there are numerous Pay Per click fraud detection software: Some examples: