Can a one-tailed permutation test really use all permutations in the denominator? In a permutation test I calculate all of the permutations that could have given rise to an effect assuming exchangeability. In the case of a two-tailed test it makes sense to check the proportion of all of the effects from the permutations that are greater than the original effect and less than negative the original effect.
However, if I have strong reasons to use a (positive) one tailed test, am I really allowed to use all of the permutations that will be less than the effect, including those less than 0? If I have strong reasons to believe the only possible effects are positive then shouldn't I have to exclude all permutations that result in a negative effect? I've already excluded them as possible effects and therefore they would be exceptions to exchangeability. And thus, the p-value in a permutation test is the same regardless of whether a one-tailed or two-tailed test is planned?
 A: Yes, you would still use all the permutations, even though the test is a one-sided one.  The reason is that the permutations represent the distribution of the sample values of the estimator in question, not the population parameter value, and if the sample value can be negative, well, that's the way it is.  If your estimator can return values that are outside a range where you know the true parameter must lie, that's a problem with the estimator, and should be addressed by modification of same, not by throwing out permutations that generate such a value.
To clarify, let's construct an example.  Assume I'm sampling from a Normal distribution with $\mu = 0.1, \sigma = 1$, and I know a priori that $\mu \geq 0$.  If I use the sample mean as my parameter estimate, it is possible to observe $\bar{x} < 0$.  If I want to construct a better parameter estimator, I could do so, for example, by setting $x^* = \max(0, \bar{x})$, and I'd run my permutation test using that estimator.  With the estimator $x^*$, I'm not going to see any infeasible estimates in my permutation calculations.  
This is not the same as throwing out the permutation results that are $< 0$; the modification I've used as an example would, in effect, change all the permutation results that are $< 0$ to results that are $= 0$ (but it's doing so by changing the functional form of the estimator, not by altering the permutation samples while using the original estimator).  You can see that the effect on your p-value calculation / test results may be quite different in the two cases, depending on how likely an infeasible value of the estimate might actually be.
A concrete example, albeit based on the bootstrap rather than the permutation test:  Assume we have data from a $\text{Normal}(0.1,1)$ distribution, we know that $\mu \geq 0$, and we are constructing a bootstrap test of the hypothesis that $\mu < 0.02$.  We compare two approaches: using the sample mean as our estimate of $\mu$ and throwing out bootstrap sample means $<0$, or using $x^*$ as defined above and keeping all the bootstrap $x^*_i$s.  We generate our sample of size 100 from the Normal distribution and construct 1000 bootstrap replications:
x <- rnorm(100, 0.1, 1)

xbar <- rep(0,1000)
xstar <- rep(0,1000)
for (i in seq_len(length(xbar))) {
  xbar[i] <- mean(sample(x, size=length(x), replace=TRUE))
  xstar[i] <- max(0, xbar[i])
}

which, if we run this a few times, can generate:
> mean(xbar[xbar >= 0] < 0.02)
[1] 0.01661475
> mean(xstar < 0.02)
[1] 0.053

Using the exclude-bootstrap-samples approach causes us to reject the null hypothesis, while using the improved estimator while keeping all the bootstrap samples causes us to fail to reject the null, with the same underlying sample.
