It appears it's there in the store, no idea why it wasn't restored to my phone. You just don't see it if you search for "auth" or "authentication". You'll see a lot other 3 party tools, some of them even claiming to generate 2 factor authentication codes.
You'll find it if you search for "authenticator". Bing is a really good search engine, the one in the Windows Store is really bad and always has been, why?