Linkstar, pagerank peddlers?

I was contacted by a company called Linkstar (link-star.co.uk). They wanted to place text ads on my site, for a reasonable sum of money. Fair enough, but I researched them and found some discouraging information.

Apparently, Linkstar does not place a "nofollow" attribute on their links — and I, as a publisher, would be signing an agreement not to modify their HTML code in any way.

The "nofollow" attribute is used by search engines, such as Google, to distinguish between paid and non-paid links. The search engines judge the relevance of a page in various contexts by studying the links that point to it. For this reason, it is possible to improve the ranking of a web page by introducing links to it into other (good) pages. Such manipulation is called Search Engine Optimization (SEO), and is lucrative because everybody wants their own pages to be considered relevant, and thus end up high on the results pages of the large search engines. To counter such manipulation, search engines also rank every page along a one-dimensional good–bad scale. A page is considered bad if, among other things, it contains paid links that haven't been marked as such. Of course, search engine companies have a hard time automating the enforcement of this rule, so it's possible to get away with it, but at the risk of suddenly dropping out of the results pages of search engines all over the world.

When confronted with this, Linkstar informed me that indeed, their links would not include the "nofollow" attribute. They gave me a semi-plausible explanation, involving technical limits of their ad tracking system.

I politely declined their offer, and would recommend others to do the same. I don't know whether Linkstar is a legitimate advertising agency, as claimed, or the back end of a search engine optimization company. I'll give them the benefit of the doubt as for their intentions, but will not risk my own pagerank.