The minimum Rent_Period requirement in the above construction can be removed by using RSA accumulator described here. An additional field for revival_counter is to be added to the account data for the contract. revival_counter represents the number of times the contract was revived. An RSA accumulator along with the state root are to be maintained as part of the block.
RSA accumulator is used to accumulate entries for all the deletion transactions in a block. The accumulator will be cumulative and hence it will contain deletion entries for all the contracts across blocks. A deletion entry for a deletion transaction is calculated as hash(address, revival_counter). The above question of How do you make sure that it has not already been revived? can be solved using this mechanism. A user provides 2 proofs, a proof of existence of deletion entry in the accumulator for some revival_counter R and a proof of non-existence in the accumulator with R+1 as revival_counter for that contract. This ensures that the contract was not revived in between those proofs and we know the current revival_counter value. This construction ensures that there is no minimum time period for which contract should be active after revival.
Any feedback on the above construction or any issue regarding storage rent that is not addressed is very much appreciated.