Lantern20, it sounds like you got a runaround. First, the answer you got, that it had to do with a price change is wrong. As a WP Developer I can tell you that price changes do not affect licensing. Once you have the license, it's yours to keep. If an app is set to free (as Liquid Daffodil has done several times with all of their apps), and later raised to some price, all of those who installed while free will still have the same license as those who are now paying, which includes updates. My suspicion is that there was some glitch in the store, which has happened several times, and the person who gave you the above reason either didn't know or didn't want to tell you the truth. My bet is the latter.
Several times there have been glitches in the store where people reinstalling were required to re-purchase an app. In those cases, if you contacted support they would refund the re-purchase. It hasn't happened to me that I can think of, but it's been a story here on the WPCentral blog a couple times.
And as has been said, apps can be removed from the store, and no longer be available. Sometimes it's the developer removing it for some reason (hide it in the store to keep new installs from happening while working out a bug, for instance), or Microsoft removing them from the store. One example of this is if a developer decides to no longer be a WP developer and pay the $99 now $19 developer registration fee, and his annual registration expires, his apps will be removed from the store, as his relationship with Microsoft has expired, so they can no longer "sell" his apps IAW the T&C of the agreement.
HTH.