Forgot to add that I also made the mistake of uninstalling Vlc at some point. It was still working. But then I couldn't get it back because the app store didn't let me install it any more.
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.