"eBay has no idea if online ads work" would be a better title. Or "eBay can't get their online ads to work".
If you looked at eBay's search advertisements in the last years you probably have seen very ridiculous ones, like:
Love.
Buy it cheap on eBay
Low Prices. New and used.
As a control they take MSDN/Yahoo vs. Google. The control should be a different advertiser, not a different advertisement network.
In the paper they mention removing the term "eBay Shoes" from their keywords, because they rank organically for that. They should have never added it, because it is a bad keyword for them. They should advertise on the brand name shoes they are selling. This ties back to the bad adverts by eBay: Fixing your mistakes and seeing change, is different from performing a controlled experiments on a healthy advertiser.
They muse about "the types of consumer that may already be informed about the advertiser’s product". This adds a few problems: those customers may have been informed through the very advertisements they now claim don't work. Suddenly shutting down advertisements does not negate the effects of running advertisements years before that. The paper does not investigate the effect that ads have on brand recognition and brand trust. Usability tests show people clicking on advertisements first, because then they expect quality and a simple commercially interesting proposition.
I do think the problem they are describing "some customers may be so aware of a brand, that advertising to them becomes worthless" is valid. Maybe ad networks could help here and implement a form of "demarketing" next to their "remarketing" options: Once a user has enough knowledge of the brand, stop advertising. But a better (and currently available) method could be to apply remarketing and give these power users tailored advertisements. An example could be a buyer's program, promoting a new product from a well-purchased brand, or a referral bonus. To continue offering them advertisements like "eBay shoes" does not make much sense.