While it's an obstacle, I don't think this is as big of an issue as they make it out to be, and I say this as someone who runs a DIY crawler and a janky homebrew search engine. You can get listed as a good bot with cloudflare &c if you ask nicely enough. Even if you aren't, their IP ranges are public so you can crawl them really slowly if you absolutely must have their stuff.

In the end, you are never going to get completeness, that's a bad mark to aim for, and not even Google does that. That goal requires you have a model of the Internet that's as old as Vannevar Bush. The Internet isn't a bunch of static files on a souped up FTP server anymore, most pages are generated request-time, increasingly client-side. There are websites that don't just have infinite documents, they have infinite wildcard subdomains as well. There are websites that give you different results depending on what time of day it is, or where you are from.

The hard problem of search engines is to find a good subset of the internet for some definition of good; and the first step toward doing that (in a timely fashion) is to rein in the crawling. Search engines are always always going to present a selection of web sites, and there are always going to be pages you can't find because they didn't make the cut; either because they were excluded, or because they excluded themselves.