How can I get the latest compatible app version?
Ok, this is not exactly what I was looking for, but it works... it is more like a preventive approach.

So, my solution would was to install Titanium Backup (which requires root access to work) and backup all my apps. Then, whenever I need more space, I just backup my apps before I go on. If I need them again, I can use Titanium Backup and restore.

And this is why I consider it a preventive approach: it is all about regular backups.

If anyone knows a better way to do this, please share =)