I'd assume they would have a record of the user in their database. How else would they earn money from the data harvesting their app is a cover for? For the small number of apps that aren't solely data harvesting, surely they still have records of their users in a database as well? This question almost reads as if you're assuming the only record of an app would be through the store and not by the app developers themselves. I would find that truly shocking and quite comically sad if true.

It seems like it would be trivial for a user to login to the app acquired from a different store to be able to display a "welcome back" or even something along the lines of a "restore purchases" type of thing.

This can't be reinventing the wheel kind of a thing.