A search engine that literally covers all of the Fediverse with no exception has to even know about brand-new instances that have just been started a split-second ago. An instance that’s so new doesn’t even have any connections into the Fediverse yet, probably no content and only one account, the admin account. (Replace “account” with “channel” on Hubzilla and (streams).)

So if someone spins up a new instance of whatever project, that search feature has to know about that instance immediately before the instance even connects with anything.

Yes, but who would want a search engine to specifically cover emtpy servers with half a nanosecond lifetime? For all practical intents and purposes, people search for content, which already excludes these theoretical edge cases. More realistically, people will search for quality content, which implies some engagement happened and some upvotes accumulated. There is no value in discovering servers before users discovered them, on the contrary.

If you really care about new and empty servers, you're rather looking for a fediverse monitoring tool than a search engine. And even for those, it's questionable what the value of those entries would be. I would prefer if they are filtered out to not bloat the numbers.