You can make an app no longer available for sale without removing the ability to download it for existing customers. That's all that is really needed. You can also create bundles that discount for new purchasers if they own the old one. I've seen this done by a few people.
It's not something that is well supported, but it's not infeasible.
> Links on the web to your app die since the links go to the old version, people who see your app recommended click the link and think the app is gone.
Links to the store listing page, yes, but also I wouldn't trust those links to work permanently anyway, I'd create a redirect page in my control.
Deep link connections into apps are evaluated at install time, so if a user installs a new version and the site allows this, that should transition correctly.
> You can't keep supporting users of older versions with simple bug fix releases without leaving the app live on the store, which confuses users into buying the old version of the app.
I would suggest stopping updates. If you're disciplined about software releases you can burn down the list of bugs to the point that it's negligible towards the end of the major version, and then close it as no longer updated. Bugs on new OSes are out of scope, a good reason for users to update.
> You can't sell upgrades at a discount price (which is common in any other software market)
I'm pretty sure I've seen this done via an admittedly awkward use of bundles. Alternatively a soft launch to existing users with temporary discount seems very common.
> Just user confusion in general.
This feels solvable, and it's not like the current situation doesn't result in confusion. We have plenty of confusion, so it's just about figuring out the better option. This will vary by userbase.