Developers can decide to allow the download of the latest compatible version for old devices, but it seems a lot decides to against it. So unless you manually backup the apps, it's really a pain to restore things on old devices.

Don’t try to install it from its store page, but from your “Purchased” list on your account. That should get the latest version you had access to. I haven’t tried that in years, so something may have changed.

I made this same mistake with an old iPod. It would have been nice if Apple had at least warned me on uninstall before slapping me in the face. That was the last day I used that device.

I've received an old iPad to play around with running iOS 9. Safari is essentially crippled by a lack of software updates but old versions of the apps can still be installed.

Because of Apple's great software design, you need an old version of iTunes. From there, you can add apps to your account. Then, on the iPad, you can install "purchased" apps. The store itself is completely useless as nothing will install, but the "purchased" page will let you download the last version that works on the device.

I don't have the iPad any more. I'm not sure Vlc would still show up as "purchased" once I uninstalled it.

Even free apps you download are technically purchased (for the price of $0.00). My purchase history still shows some free games I downloaded in 2013