Is sampling at double the desired reproduction frequency accurate? This is probably a general principles question, though I'm thinking specifically in relation to sound, which is commonly sampled at a rate of 44.1 kHz in part because the maximum frequency the average person can hear tops out at around 20 kHz.

Given that the sampling theorem says the sampling frequency must be greater than twice the maximum frequency one wishes to reproduce, that means you need a sample rate of at least 40 kHz if you're trying to reproduce audio.  However, isn't it the case that the theorem is establishing only the lower-bound at which accurate reproduction becomes possible, rather than the sampling rate at which accurate reproduction is guaranteed?

By way of illustration, here are some examples showing a sine wave with samples taken at twice its frequency (in each example the source data and the interval between samples is the same, and the only thing that varies is the timing of the first sample in the interval):



In the 'In Phase' example, your samples occur exactly in time with when the wave is at a peak/trough, and you get an accurate capture that could reproduce the source wave (or something reasonably like it).  I assume this represents the ideal case, and rarely happens in practice.

In the 'Out of Phase' example, however, a terrible stroke of luck has the samples occurring at exactly the same time that the source data is crossing '0' amplitude.  This results in a capture of [0,0,0,0], which I assume can only reproduce as silence.  If so, that's not accurate at all.  I assume this represents the worst-possible case, and also rarely happens in practice.

In the 'Mid-Phase' example, the samples occur midway between the source data's peaks and troughs.  This captures a sine-wave pattern ([1,-1,1,-1]), but at half the amplitude of the source signal.  That doesn't seem like adequate accuracy for proper reproduction of the source.  I assume some variant of this scenario (where the sample rate is neither perfectly in-phase nor perfectly out-of-phase with the source) is the most common practical case, by far.

Thus it seems like if you sample at double the target reproduction frequency, most of the time your recorded data will have the wrong amplitude.  It may occasionally be accurate, but it's also just as likely to occasionally miss the signal completely.  

Is this correct?  And if so, what is the sample rate one needs to use to make accurate reproduction guaranteed rather than merely possible?

If that can only be answered by imposing some constraints upon the definition of "accurate reproduction", let's say there must be zero chance of capturing silence wherever a signal is actually present, and that the recorded amplitude must always be accurate to within 5% of the actual source.
There is not only one sampling rate that theoretically allows exact reproduction. The sampling theorem states that it is sufficient for perfect reconstruction if the sampling frequency $f_s$ is greater than twice the highest signal frequency:

$$f_s&gt;f_{max}\tag{1}$$

Without further restrictions, Eq. $(1)$ is also necessary for baseband signals occupying the whole frequency range $[0,f_{max}]$. Some people like to discuss whether in $(1)$ there should be a "greater or equal" sign or just a "greater" sign. In practice, this question is totally irrelevant because you always have to sample at a frequency twice the maximum frequency plus some extra tolerance to allow for non-ideal filters.

As you've noticed, sampling a sinusoid at exactly twice its frequency will generally not allow you to reconstruct it. As soon as you sample at a rate slightly larger than twice its frequency you will be able to reconstruct it perfectly.

Note that there is band pass sampling for band pass signals where the sampling rate can be considerably smaller than twice the highest signal frequency for perfect reconstruction to be possible. However, it's generally not true that sampling at twice the signal's bandwidth is sufficient, even thought that may be the case for specific signals.

These are only the basics of (uniform) sampling of 1-dimensional signals. There is much more to be learned. Browse the "sampling" tag on this site, and read the overview article Sampling - 50 Years After Shannon by M. Unser.