One thing my colleague was able to establish - if you remembered to remove app link button from one app, you will indeed be able to create an app link with the same name in different app. So that's one thing kind of resolved at least.
However - if you deleted the app completely prior to deleting the app link within it, the names of app links are still reserved unfortunately. And the second issue - i.e. not being able to create 2 app links with the same name - is still ongoing and we haven't come up with any solution to it yet.
If anyone has any ideas on how we can handle it - please let us know.