This app store thing just burned me pretty bad when I cleared my machine and did not back up Airmail 2. When I went back to install it, It was no longer on the app store and I was informed that there was no way to get it again unless I paid for Airmail 3.

This is where just having a license key and a dmg somewhere is preferable.

Transmit v4 still is in my list of Purchased apps, and appears installable.

Look in your "Purchased" apps list, it will still be there.