Liftoff!

It doesn't seem that way. It seems like at least one person from your instance needs to have interacted with a community on another instance before it'll be included in partial match search results. If you manually navigate to one of the instances you federate with and look for a very small community there and then go back to your instance and search for some of the words in that community's name I don't believe it will come up. But then it you search for the community's exact fully qualified identifier it should come up and then once you subscribe it should come up if you try the previous search terms again. At least that's been my experience. As a result, to flesh out my subscriptions I've spent time manually browsing to other instances, finding interesting communities in their catalogue and then manually copying the identifier and then tabbing back to my instance to find the community with the identifier and subscribe, which admittedly is far from an ideal experience. Luckily I think there's a lot that the upcoming client implementations can do to make this discovery process easier.