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.