First of all, I am still not sure whether cstheory is well adapted for this question, so I won't be offended if the crowd thinks it is not the case...
In search engine marketing, several problems are interesting. Design of fair (and profitable) auction mechanisms and computation of optimal bidding strategies under bounded monetary resources are two examples of interesting (and well documented) problems.
Another problem of interest is the one of keyword selection: how to select the most profitable keyword (without any link to the amount of money available or to the "topic" of the keyword). "Profitable" can be either giving the best revenue, or the best profit. These problem deals with uncertainty: the clickthrough rate of a keyword is not known, the conversion rate is not known either.
Are you aware of some theoretical work related to this problem?