I just tried it myself on kbin.social and you are right. If you use the search at the top of the page then it will not find your magazine. If you use the search that is part of the magazine page, then it will find your magazine.
I think your question is specifically about the search at the top of the page, the global search, correct? If so, yeah, it doesn't appear to find magazines. I don't know if it's by design or a defect.
I also tried finding your new magazine from two other KBIN instances, https://feddit.online and https://fedia.io and in both instances, using either the search at the top of the page or the search on the magazine page, I was not able to see your new magazine. And I don't think they will ever be able to because I have been unable to find any magazines that exist external to any KBIN instance that is not already added to the local server.
This is a bummer. When someone gets onto a new instance and they want to subscribe to an interesting magazine, I don't see any way that they can find them outside of their local instance.
I'd love to be wrong about this. Has anyone had a different experience?
Bohammer