> but you cannot obviously reinstall it

From the App Store, no, but from your iTunes backups you can. All you need is the .ipa backup file associated with a purchase under your Apple ID.

I've got this for several apps (iMAME and Gridlee, to name two) that Apple's done similar to.

Thanks! That makes sense, I would be pretty pissed if they removed apps from user devices too without their consent.