@Lilkev Thanks for letting me know that the functionality does exist in the app. I played around with it and have now figured out what the problem was.
First of all, I'm used to a list of communities (whether I'm subscribed to them or not) appearing as I type in Joey for Reddit. Ie, if I type in "star" Joey would list starcraft, startrek, starwars and so on. Artemis doesn't work like this. (Which is fair enough by the way, it's just that I wasn't used to Artemis's behaviour and stupidly assumed it would work like the other app.)
Secondly though, even after I hit enter in the search bar after my search term, nothing appeared. Ie, pressing enter after entering, say "music", did not initiate the search.
It was only after playing around for a while that I realised I actually had to click on "Find magazines with <search term>..." to initiate a search for unsubscribed magazines. This I think is is confusing because the "Find magazines with..." looks like an informational message, not a clickable action button.