If you don't think adsense is just as interesting as search in the core technical algorithms, you probably haven't really thought about it at all.
Agreed that it is a far from trivial problem, but the dataset is relatively limited in comparison the biggest hurdles are to get it to match up with a reasonable ad on first delivery within a given timespan, to track all the statistics and especially to combat click fraud in the network.
But in the end, without a search engine to display those ads on google would be just another advertising agency, and in many ways they are.
A better example of an interesting challenge would be to transform google news in such a way that it would show you only relevant news. There is a lot of room for improvement there and it would boost natural language processing a lot to have the tech to do that.
Any piece of tech has interesting components, but that's a relatively small part of the whole, and the money is made in the drudge-work, that was exactly the point.
From a start-up perspective, the 'core' engine of the product is probably relatively complete by launch day, but the infrastructure to make it scale, to market and monetize it, which is going to be a whole lot less sexy, is where the money eventually will come from.
Just like only showing relevant news is an interesting challenge, so is only showing relevant ads. Advertisers don't want to show you ads you're not interested in; they want to show you ads you'll actually find useful. In many ways, that's a much more interesting challenge than showing relevant news.
Extending the advertising example, it's also a very interesting challenge to show people that highly-targeted ads can be a good thing. Just like it's an interesting challenge to convince advertisers to use your ad platform. Although they are not technical challenges, they are very interesting business challenges.
Matching relevant news to a person is a completely different class of problem.
I would argue that developing the original work for displaying relevant adsense ads would appeal more to the algorithm developer than scaling out search would.
Edit, I re-read your post and you seem to realize this so I don't understand where you were going with your comment in the original article.
I could have probably picked a better example because, as has already been pointed out there are lots of interesting sub-problems in keyword based advertising.
Maybe I should have used an online advertising agency as the example, with the ad-matcher as the example of an algorithmically interesting item and the reporting, the statistics and the help desk as the infra structure.