While it has problems of its own, instances could pool and share that knowledge. The first time an instance talks to a different insta ce it could just ask “hey, what other instances are you aware of?”. The main issue there is just instances obsessively sending exponentially growing lists of instances back and forth.

But no, that is the main bane of federated social media, discoverability without a center of truth