Suppose an application regularly creates and deletes tables (for example, temporary tables). In such a scenario, there will always be such a temporary table when pruning runs, and its regions will be recorded for that time. However, the region will be deleted before it ever compacts or flushes, and it will never record prune information. Because all prune times have such regions, there will never be a set of transactional regions that all have prune info, and pruning will never happen.
The fix is to exclude deleted tables from the list of regions at each time. This is all regions of deleted tables (tables that do not exist any more), not deleted regions: a region may disappear due to a split and its data will be in new regions.