The increasing reliance on safety- and security-critical artificial intelligence (AI) has made the effectiveness of neural network authentication increasingly crucial. In particular, "patch attacks," such as adversarial patches or lighting conditions that obscure portions of an image, such as traffic signs, are challenging real-world use cases. PREMAP has achieved significant progress in authentication against patch attacks by utilizing under- and over-approximations of a preimage, a set of inputs that lead to a given output. While versatile, the PREMAP approach is currently limited to medium-dimensional fully connected neural networks. To address a broader range of real-world use cases, we present novel algorithmic extensions to PREMAP that incorporate tighter bounds, adaptive Monte Carlo sampling, and an improved branching heuristic. These efficiency improvements significantly surpass the original PREMAP and enable extension to previously intractable convolutional neural networks. Furthermore, we demonstrate the potential of the preimage approximation methodology for analyzing and verifying reliability and robustness in diverse use cases, such as computer vision and control.