As opposed to the general BitTorrent world?
Yes. Did you ever stop to wonder why people left KaZaA, eDonkey, Gnutella and so on for Suprnova and The Pirate Bay? We tried it 10-15 years ago and it was vastly inferior to torrent sites, what's new? Except that torrent sites have now gone torrentless and trackerless to mostly carry magnet links.
How exactly would a decentralized searched engine have to cope with worse problems than the traditional ones struggle with?
Statistics. Google has tons and tons of statistics on what links are actually relevant to the search terms, your decentralized crawler will find some random shit and return it as a hit. Search any of the networks above and you get tons of crap. Perhaps you get better results with a decentralized search engine on the web, but only because you rely on sites like TPB and other popular torrent sites to weed out most of the crap. Searching a fairly centralized resource in a decentralized way isn't exactly being decentralized.