As annoying as this is - and I agree that they should provide an option to charge for upgrades - the problem can be alleviated to a large extent by in-app purchases.

Suppose for example you have FooApp 1.x, and you later want to release a major update, FooApp 2. You release FooApp 2 as a separate app for new customers, and provide an update to FooApp 1.x which lets existing customers update.

This is admittedly awkward, and can only really work for upgrades where the main new things in the new version are additional features. For apps which have major architectural changes it would be problematic. To the best of my knowledge though this is the best we can do in the context of the current policies.