I now understand much better what was worrying me about paired versus unpaired t-tests, and associated p-values. Finding out has been an interesting journey, and there have been many surprises along the way. One surprise has resulted from an investigation of Michael's contribution. This is irreproachable in terms of practical advice. Moreover, he says what I think virtually all statisticians believe, and he has several upvotes to back this up. However, as a piece of theory, it is not literally correct. I discovered this by working out the formulas for the p-values, and then thinking carefully how to use the formulas to lead to counter-examples. I'm a mathematician by training, and the counter-example is a "mathematician's counter-example". It's not something you would come across in practical statistics, but it was the kind of thing I was trying to find out about when I asked my original question.
Here is the R-code that gives the counter-example:
vLength <- 10; meanDiff <-10^9; numSamples <- 3;
pv <- function(vLength,meanDiff) {
X <- rnorm(vLength)
Y <- X - meanDiff + rnorm(vLength,sd=0.0001)
Paired <- t.test(X,Y,var.equal=T,paired=T)
NotPaired <- t.test(X,Y,var.equal=T,paired=F)
c(Paired$p.value,NotPaired$p.value,cov(X,Y))
}
ans <- replicate(numSamples,pv(vLength,meanDiff))
Note the following features: X and Y are two 10-tuples whose difference is huge and very nearly constant. To many significant figures, the correlation is 1.000.... The p-value for the unpaired test is around 10^40 times smaller than the p-value for the paired test. So this contradicts Michael's account, provided that one reads his account literally, mathematician-style. Here ends the part of my answer related to Michael's answer.
Here are the thoughts prompted by Peter's answer.
During the discussion of my original question, I conjectured in a comment that two particular distributions of p-values that sound different are in fact the same. I can now prove this. What is more important is that the proof reveals the fundamental nature of a p-value, so fundamental that no text (that I've come across) bothers to explain. Maybe all professional statisticians know the secret, but to me, the definition of p-value always seemed strange and artificial. Before giving away the statistician's secret, let me specify the question.
Let $n>1$ and choose randomly and independently two random $n$-tuples from some normal distribution. There are two ways of getting a p-value from this choice. One is to use an unpaired t-test, and the other is to use a paired t-test. My conjecture was that the distribution of p-values that one gets is the same in the two cases. When I first started to think about it, I decided that this conjecture had been foolhardy and was false: the unpaired test is associated to a t-statistic on $2(n-1)$ degrees of freedom, and the paired test to a t-statistic on $n-1$ degrees of freedom. These two distributions are different, so how on earth could the associated distributions of p-values be the same? Only after much further thought did I realize that this obvious dismissal of my conjecture was too facile.
The answer comes from the following considerations. Suppose $f:(0,\infty)\to (0,\infty)$ is a continuous pdf (that is, its integral has value one). A change of coordinates converts the associated distribution into the uniform distribution on $[0,1]$. The formula is
$$p=\int_t^\infty f(s)\,ds$$
and this much is explained in many texts. What the texts fail to point out in the context of p-values is that this is exactly the formula that gives the p-value from the t-statistic, when $f$ is the pdf for the t-distribution. (I'm trying to keep the discussion as simple as I can, because it really is simple. A fuller discussion would treat one-sided and two-sided t-tests slightly differently, factors of 2 might arise, and the t-statistic might lie in $(-\infty,\infty)$ instead of in $[0,\infty)$. I omit all that clutter.)
Exactly the same discussion applies when finding the p-value associated with any of the other standard distributions in statistics. Once again, if the data is randomly distributed (this time according to some different distribution), then the resulting p-values will be distributed uniformly in $[0,1]$.
How does this apply to our paired and unpaired t-tests? The point is in the paired t-test, with samples chosen independently and randomly, as in my code above, the value of t does indeed follow a t-distribution (with $n-1$ degrees of freedom). So the p-values that result from replicating the choice of X and Y many times follow the uniform distribution on $[0,1]$. The same is true for the unpaired t-test, though this time the t-distribution has $2(n-1)$ degrees of freedom. Nevertheless, the p-values that result also have a uniform distribution on $[0,1]$, by the general argument I gave above. If Peter's code above is applied to determine p-values, then we get two distinct methods of drawing a random sample from the uniform distribution on $[0,1]$. However the two answers are not independent.