> Which leaves only one hypothesis - that this is somehow related to advertising.

Of course it is, they'll earn more if it takes you longer to search and you are more likely to click on one of the ads. I think it's as simple as that.