> my understanding is that originally deep links required a special non-domain to be registered that was separate from a normal web url.
You might be thinking of protocol handlers, like oacon:// to open something in software installed to handle that (in this case, launching openarena to connect directly from a dpmaster mirror with such application links included). I don't think they were called deep links back then, just different protocols, like http in http://example.org is a protocol that your browser is configured to handle and ftp:// used to be as well
These are still in relatively common use today, but on mobile devices it has become the norm to hijack specific domain names or even a path (e.g. F-Droid will try to handle repositories on third-party domains for you by trying to hook¹ any URL that contains */fdroid/repo/* -- so far, this has always been useful to me, but I can see the flip side). This link hijacking is often a pain for me as anyone linking to any Google product will make my phone try to open some Play Services component, which is largely not functional. I can't get rid of the system component (e.g. replace it with microG) without installing a custom ROM, which I can't do without getting rid of half the device's special features (no point having this phone then), but I also don't want it pinging back to the mothership so... a pain it shall be
As for your problem, reset the app's settings and it'll re-prompt you the next time you click one of these links in which app these links should open. It should do that any time there is (newly) more than one app that can handle any given URL
¹ https://github.com/f-droid/fdroidclient/blob/be028d71c2a25b9...