Redundancy removal, i.e., identifying and eliminating redundant logic, is an essential optimization strategy for decreasing design area, reducing critical path delay, and simplifying circuit testability analysis. However, redundancy removal strategies invoke time-consuming proof engines with worst-case exponential behavior. While continual enhancements to heuristics resident in these engines result in large average runtime improvements, inherent intractability still leads to sub-optimal optimization and occasional large runtime outliers. Such outliers are unacceptable in an industrial setting where an outlier compromises design turnaround time. Our work introduces a semi-local optimization algorithm that mitigates the inherent intractability in redundancy removal and eliminates crippling runtime outliers. We further embed this algorithm within a framework that minimizes any negative impact to delay and area metrics. Using a cutting-edge industrial tool , we demonstrate 1) statistical neutrality in area and timing while achieving consistent runtime improvements on a large set of proprietary circuit designs of varying type and complexity and 2) over 50% runtime improvement on a suite of computationally intractable industrial designs, even when measured at the end of the physical synthesis flow.