In the Envelope Paradox player 1 writes any two different numbers $a< b$ on two slips of paper. Then player 2 draws one of the two slips each with probability $\frac 12$, looks at its number $x$, and predicts whether $x$ is the larger or the smaller of the two numbers.
It appears at first that no strategy by player 2 can achieve a success rate grater than $\frac 12$. But there is in fact a strategy that will do this.
The strategy is as follows: Player 2 should first select some probability distribution $D$ which is positive everywhere on the real line. (A normal distribution will suffice.) She should then select a number $y$ at random according to distribution $D$. That is, her selection $y$ should lie in the interval $I$ with probability exactly $$\int_I D(x)\; dx.$$ General methods for doing this are straightforward; methods for doing this when $D$ is a normal distribution are well-studied.
Player 2 now draws a slip at random; let the number on it be $x$.
If $x>y$, player 2 should predict that $x$ is the larger number $b$; if $x<y$ she should predict that $x$ is the smaller number $a$. ($y=x$ occurs with probability 0 and can be disregarded, but if you insist, then player 2 can flip a coin in this case without affecting the expectation of the strategy.)
There are six possible situations, depending on whether the selected slip $x$ is actually the smaller number $a$ or the larger number $b$, and whether the random number $y$ selected by player 2 is less than both $a$ and $b$, greater than both $a$ and $b$, or in between $a$ and $b$.
The table below shows the prediction made by player 2 in each of the six cases; this prediction does not depend on whether $x=a$ or $x=b$, only on the result of her comparison of $x$ and $y$:
$$\begin{array}{r|cc}
& x=a & x=b \\ \hline
y < a & x=b & \color{blue}{x=b} \\
a<y<b & \color{blue}{x=a} & \color{blue}{x=b} \\
b<y & \color{blue}{x=a} & x=a
\end{array}
$$
For example, the upper-left entry says that when player 2 draws the smaller of the two numbers, so that $x=a$, and selects a random number $y<a$, she compares $y$ with $x$, sees that $y$ is smaller than $x$, and so predicts that $x$ is the larger of the two numbers, that $x=b$. In this case she is mistaken. Items in blue text are correct predictions.
In the first and third rows, player 2 achieves a success with probability $\frac 12$. In the middle row, player 2's prediction is always correct. Player 2's total probability of a successful prediction is therefore
$$
\frac12 \Pr(y < a) + \Pr(a < y < b) + \frac12\Pr(b<y) = \\
\frac12(\color{maroon}{\Pr(y<a) + \Pr(a < y < b) + \Pr(b<y)}) + \frac12\Pr(a<y<b) = \\
\frac12\cdot \color{maroon}{1}+ \frac12\Pr(a<y<b)
$$
Since $D$ was chosen to be everywhere positive, player 2's probability $$\Pr(a < y< b) = \int_a^b D(x)\;dx$$ of selecting $y$ between $a$ and $b$ is strictly greater than $0$ and her probability of making a correct prediction is strictly greater than $\frac12$ by half this strictly positive amount.
This analysis points toward player 1's strategy, if he wants to minimize player 2's chance of success. If player 2 uses a distribution $D$ which is identically zero on some interval $I$, and player 1 knows this, then player 1 can reduce player 2's success rate to exactly $\frac12$ by always choosing $a$ and $b$ in this interval. If player 2's distribution is everywhere positive, player 1 cannot do this, even if he knows $D$. But player 2's distribution $D(x)$ must necessarily approach zero as $x$ becomes very large. Since Player 2's edge over $\frac12$ is $\frac12\Pr(a<y<b)$ for $y$ chosen from distribution $D$, player 1 can bound player 2's chance of success to less than $\frac12 + \epsilon$ for any given positive $\epsilon$, by choosing $a$ and $b$ sufficiently large and close together. And even if player 1 doesn't know $D$, he should still choose $a$ and $b$ very large and close together.
I have heard this paradox attributed to Feller, but I'm afraid I don't have a reference.
[ Addendum 2014-06-04: I asked here for a reference, and was answered: the source is Thomas M. Cover “Pick the largest number”Open Problems in Communication and Computation Springer-Verlag, 1987, p152. ]
