Routability optimization in modern EDA tools has benefited from using machine learning (ML) models. However, constructing these models is challenging and their performance leaves room for improvement. Traditional neural architecture search (NAS) techniques struggle to perform well on routability prediction as a result of two primary factors. First, the separation between the training objective and the search objective adds noise to the NAS process. Secondly, the increased variance of the search objective further complicates performing NAS. We craft a novel NAS technique, coined SOAP-NAS, to address these challenges through novel data augmentation techniques and a novel combination of one-shot and predictor-based NAS. Results show that our technique outperforms existing NAS-produced and handcrafted solutions by 20\% closer to the ideal area under the receiver operating characteristic curve (ROC-AUC) in DRC hotspot detection. SOAPNet is able to achieve an ROC-AUC of 0.9702 and a query time of only 0.461 ms.