It seems that if nobody on your instance has previously interacted with a particular community from another instance, then it won't show up under "all" in the communities list.
In this situation, you should be able to search for the full name of the community (!community@instance), that should trigger a sync of that community. After that, you'll be able to subscribe.
Note that it's also possible for instance admins to block some other instances completely - in that case, you won't be able to subscribe to any communities from that particular instance.