A new two-sample randomization test is proposed for testing that the joint distribution of two samples is invariant under permutations. The $p$-value of the test has a finite sample minimaxity property over neighborhoods of completely specified alternative distributions. Asymptotically, the test has minimax Bahadur slope against the neighborhoods, which remain fixed as the sample sizes increase. The proposed test also offers the best compromise between robustness against departures from a model alternative and optimality at the model alternative in the sense that no other test with the same gross-error-sensitivity has larger slope at the model. Some modifications of the test are proposed for testing the nonparametric null hypothesis against neighborhoods of models that have a shared nuisance location-scale parameter. These nuisance-parameter-free versions of the test are justified for large samples from exponential families, and an example of their use is given.