Methods, computing systems and computer program products implement embodiments of the present invention that include configuring a mapping table to store mappings between logical and physical storage regions on one or more storage devices, and configuring recent and stable lists to store physical region numbers for non-mapped physical storage regions. A request is received to delete, from the mapping table, a given mapping including a given physical storage region, and the metadata indicating the given physical storage region is stored to a recent list stored in the memory. When the mapping table is destaged from the memory to a given storage device, the metadata is moved from the recent list to a stable list stored in the memory. Upon receiving a mapping request, a physical storage region is allocated from the stable list. If the recent list is empty, then the physical storage region is allocated from the recent list.