Deep networks have been found to be highly susceptible to adversarial attacks. One fundamental challenge is that it is typically possible for small input perturbations to produce large movements in the final-layer feature space of these networks. In this work, we define an attack model that abstracts this challenge, to help understand its intrinsic properties. In our model, the adversary may move data an arbitrary distance in feature space but only in random low-dimensional subspaces. We prove that such adversaries can be quite powerful: defeating any classifier that must output a class prediction on any input it is given. However, by giving the algorithm the ability to abstain, we show that such an adversary can be overcome when classes are reasonably well-separated in feature space and the dimension of the feature space is high, by an algorithm that examines distances of test points to training data in feature space. We further show how data-driven methods can be used to set algorithm parameters to optimize over the accuracy vs. abstention trade-off with strong theoretical guarantees. Our theory can also be viewed as providing new robustness guarantees for nearest-neighbor style algorithms, and has direct applications to the technique of contrastive learning, where we empirically demonstrate the ability of such algorithms to obtain high robust accuracy with only small amounts of abstention. Overall, our results provide insight into the intrinsic vulnerabilities of non-Lipschitz networks and the ways these may be addressed.