While I can't give an answer, here are some things that we might want to think about and which it should be easier to find literature on:
All languages?
Firstly, are we talking about all natural languages? The languages concerned may have a dramatic effect on average sentence length and types of complexity. If it is indeed the case that there are languages which effectively don't allow embedding (or in which it is severely limited), such as Piraha, then those languages will have a smaller number of words per sentence and there is more overall likelihood of sentences being repeated. Furthermore, languages like Turkish will have fewer words per sentence than a language like English. You'll also have to consider research about how inflection affects the probability of a sentence being repeated. For example, pro-drop language in which adjectives show gender agreement will have less repeated sentences than pro-drop languages which don't. In the former sentences like "it's loquacious/blue/interesting/bellicose" will be split into two (or more) groups depending on the gender of the subject making them less likely to be repeated and the latter they won't.
Age:
Secondly, are we talking about all humans or only adults and so on and so forth? Small children use very short sentences compared to adults (even when they are fully grammatical) and they also have a much more highly constrained vocabulary, so one suspects that, perhaps excluding the use of names, most of an English speaking toddler's sentences have been uttered before or will be uttered again. In Nigeria 42% of the population are under 14 and so the inclusion or exclusion of children's sentences will have quite some impact on how likely a Nigerian Hausa-speaking person's sentences are to be repeated or to have already been said. On a less dramatic scale, older adult speakers of English appear to use shorter sentences with a more limited vocabulary than younger adult speakers - thus making their sentences more likely to be repeated. So, if for some reason children's sentences were to be excluded, where the cut-off point occurs may potentially have a significant effect.
Which corpus?
Thirdly, regarding the reliability of any data that one might decide to use to come to a conclusion about this, we need to consider what type of texts the data is coming from. The type of corpora that are currently available are very unlikely to be of any use here. Most large corpora of spoken language are not corpora of natural conversation or conversations at the supermarket or of sentences spoken to bus drivers or people negotiating each other in a restaurant or on the street. In an earlier version of this question, the OP discussed combinatoric possibilities in relation to a 20 word sentence. Here, the OP presumably got their notional 20-word example sentence length from considering written corpora (more on this later). However, this disregards SMS and WhatsApp messages, for example, as well as emails and so forth. According to the Pew Research Centre, 18-24 year olds sent or received on average 109.5 SMS messages per day. The length of any sentences contained within such texts (a lot of the messages won’t contain any writing or may not contain full sentences) is likely to be quite short and, one suspects, the vocabulary more constrained, increasing the likelihood of their being reduplicated. For many millions of people this is going to be the largest body of writing that they produce in terms of numbers of sentences. Annually, according to Sellcell.com (in information that's easily replicable from many sources) humans currently send around 8 trillion SMS messages and 43 trillion Whatsapp messages per year. On a relatively quick back of an envelope calculation this would appear to dwarf the output of the 4 million books (which contain an average of 70-120 thousand words), and 5 million academic articles published every year as well as the estimated 4.7 billion indexed pages of the World Wide Web, most of which, of course, was not published in a single year! Without considering this written output the outcome of this investigation will be severely skewed. And we don't seem to have the corpora to be able to do so.
We shouldn't bother with writing
This brings us to a fourth point. Why consider written sentences at all? To start with many of the world's 7,000-odd languages have no writing system, and many others have had one invented but it is rarely ever used. Even in those societies in which some people write relatively often, there is still no doubt that for the vast, vast majority of people, people speak far, far more than they write. Onnela et al suggest that male and female English speakers speak around 16,000 words per day, far outreaching the most prolific of writers! The importance of this is two-fold. Firstly the chance of a sentence being repeated increases the greater the number of sentences uttered. The second is that spoken sentences are, on average, much shorter than written ones (- or the written ones that you see in large corpora taken from specific types of texts, novels, newspapers and so forth). In a description task in Nippold (2013), the average utterance length varied between 10 and 13 words depending on the task. It's possible that in most environments it would be shorter still, not longer. In any case, the vast, vast, vast majority of sentences are spoken and not written and we shouldn't let written corpora skew or sully our data or our picture of the task at hand.
Time
Turning to the fifth point, you may have noticed that I talked about the possibility of a sentence having already been said or being said in the future. The standard varieties of many languages seem to have become fairly stabilised, perhaps due to the different types of media that they dominate, and the English of 100 years ago is barely different in any substantive way from the English of today. We might assume that things might continue in this vein for the next hundred or few hundred years too. So the question then becomes how far into the past and future do you want to look? The likelihood of a sentence being repeated obviously goes up the longer you wait, and also the greater the population becomes. There is an old addage that if a monkey bashes away randomly on a typewriter for an infinite amount of time it will eventually produce the works of Shakespeare ...
Language is a combinatorial system, but ...
Lastly, let's consider the often raised question of combinatoric possibilities. In an earlier version of this question, OP wrote:
[The fact that most sentences are said or written only once] seems obvious considering the combinatoric explosion of possible sentences that results if we multiply even a low number like 1,000 possible word-choices for each word in, say, a 20-word sentence. That's 1060 possible sentences right there, far more than even 8 billion people could say if they each said one unique sentence every second for 200,000 years, and we haven't even considered sentences of different lengths yet.
Well, we need to adjust some of these figures. First of all, as noted earlier, most spoken sentences are much shorter than 20 words. Considering the results from Nippold’s research cited above, let us assume an average sentence length of 11 words. Now, as we start to say a sentence, the words we choose radically close down the number of possibilities available to us for the following word. In addition, many word classes which will be required in the construction of grammatical sentences, for example determiners, have very few members only some of which will be live possibilities in a given environment. In his paper Words and Rules, Steven Pinker writes:
[Our] knowledge of language is couched in abstract symbols that can embrace a vast set of concepts and can be combined freely into an even vaster set of propositions. How vast? In principle it is infinite; in practice it can be crudely estimated by assessing the number of word choices possible at each point in a sentence (roughly, 10) and raising it to a power corresponding to the maximum length of a sentence a person is likely to produce and understand, say, 20. The number is 1020 or about a hundred million trillion sentences (Pinker, 1994).
What Pinker is calculating here is the expressive power of the language, in other words the number of theoretically possible sentences. However, what we are interested in is actually uttered sentences. With this in mind let's take our notional sentence length of 11 words and use Pinker’s estimate of 10 possible word choices at any given point. This gives us 1011 possible sentences. Sentences shorter than this can be simply accommodated by positing blank words at the end of a sentence.
Now, there are currently 620 million native English speakers in the world—we will ignore the tiny percentage who can't speak because they are babies, or for other reasons—who are averaging, according to Onnela et al, 16,000 words per day. Assuming an eleven-word average length sentence this correlates to 1455 sentences per day. And they’re doing this for 365 days of the year. This gives us a back of the envelope figure of 3.3 x 1014 English sentences uttered every year – which seems to be significantly higher than the 1011 suggested expressive capacity.
However, I do not have much faith in Pinker’s estimate of 10 possible words at any given point. His own calculation ignores the fact that the first word, or the word functioning as head of the subject noun phrase in any given sentence is not nearly so highly constrained. Having experimented with various sentences it seems that for certain words the number of possibilities is many orders higher.
But in any case, I am going to argue that such simple combinatoric calculations are deeply misleading. The reason is that they ignore frequency and probability. Although, depending on how you measure it, most adults know around 18-25,000 words, most of us only use a very few thousand in our day to day spoken utterances. In fact, it has been shown again and again, in relation to English, that just the 100 most frequent words in English account for over 50% of the text in several well-respected corpora, for example the Oxford English Corpus. The fact of the matter is that, as mentioned in this Language Log post most words are very rare. So if one is going to try to calculate how likely a spoken utterance is to be repeated, you need to know how likely a sentence is to have relatively frequent words in it and how frequent (and therefore likely to be reproduced in a given utterance) those words are going to be. Intuition and the facts just mentioned tell us, of course, that not only are sentences like She hit him more likely to be repeated than The sesquipedalian chihuahua prevaricated, they are also more likely to be uttered in the first place and will therefore take up a large proportion of the natural language sentences that are uttered.
Because of the issue of word frequency (and construction frequency for that matter), if we are to try to calculate the likelihood of an unspecified spoken sentence being repeated (or having been said already), we would need to have a sound understanding of Zipf’s law, which correlates a words rank with its predicted frequency, and a much better understanding of probability than I could ever possible grasp. It seems to me that this is an extremely complicated issue which would be difficult, if not possible to resolve.
Parting thought
[I'm currently waiting for clarification from OP about the data below before I edit this section. The 10% mentioned below is going to be somewhat smaller, although it's not clear how much. However, whether it's 10, 7 or 5% the general principle holds!]
I leave you with the following thought. Here is Pinker’s claim:
- Virtually every sentence that a person utters or understands is a brand-new combination of words
Now, in preparation for this question, Ben Kovitz, OP, did a rough and ready search of the British National Corpus (commonly referred to as the BNC). He found that they had a total of roughly 6 million sentences, out of which roughly 600,000 were duplicates, slightly more than 10%. So, even in a relatively small corpus (compared, for example to the 19.6 billion word News on the web or NOW corpus), a full 10% of the sentences were duplicates. This therefore blasts out of the water Pinker’s claim that virtually every sentence ever uttered is unique. That 10% figure would, of course, be much higher if the corpus wasn’t distorted by an overrepresentation of written text giving an average sentence-length of 16 words. It would also be much higher in a much bigger corpus. Pinker's sold us a stinker!
