blinding flash of the obvious - when doing permutation testing, it's enough to keep only the results that are more significant than the real ones, and only do permutations for as long as you are not sure the result is not significant.

Still need to do a lot of permutations for the significant findings, but for all else - let's just say that the users of the 'long' queue in the computing farm will be happy :)