For 44 claimed phonemes, we need 44*43/2 = 946 minimal pairs. If we can't find even one of them, then it is possible to claim that English has 43 phonemes and not 44 due to complementary distribution (with a complicated rule). Hence I'm interested if there is any work trying to count phonemes rigorously?
In theory, any language could be analyzed as having only two phonemes,
/1/. Then we could say
[p] is the realization of
[t] is the realization of
[k] is the realization of
/00010/, and so on.
The problem is, this isn't an especially useful analysis. It doesn't reveal any new insights about the language, or make it easier to discuss sound changes, or anything like that.
Since phonemes are fundamentally a theoretical construct, not an externally-measurable one, what really matters is how useful they are. Do they explain the data in a concise way, and make it easier to analyze it? That's the true metric, more so than minimal pairs. Even though there's never going to be a minimal pair between
[ŋ] in English (one only appears in the onset of a syllable, the other only in the coda), they act completely differently, and it doesn't really help anything to call them allophones.
For another illustrative example, look at different analyses of Mandarin vowels. Some linguists say that
/y/ is phonemic in Mandarin, while others say it's merely an allophone of
/ɥ/. But you'll never find a minimal pair, because linguists who prefer the first analysis say that every syllable needs a vowel in it, so you'll never see
/ɥ/ alone without a vowel. (Linguists who prefer the second analysis say you can have syllables without phonemic vowels in them, and when you've got a
/ɥ/ in a vowel-less syllable, you get
[y].) Neither analysis is necessarily right or wrong, since both of them can explain all the data. So it comes down to elegance, utility, and personal preference.
Even if you had a full set of minimal pairs, that actually would not rigorously establish the number of phonemes in English because it doesn’t tell you how the phonemes are segmented: you could make the number larger by treating phoneme sequences in the current analysis (like /sw/ /tw/ /dw/) as single phonemes, or smaller by treating single phonemes in the current analyses as sequences (e.g. [s] as /hz/).
In general, I don’t think it is common to seriously consider minimal pairs to be the primary practical or theoretical criterion for establishing a phoneme inventory. They are a useful way of demonstrating a phonemic contrast.
As an addendum to the other answers, I'd like to observe that some languages lend themselves to minimal pairs, whereas others do not. This is a function of syllable structure, and probably to some extent the size of the phonetic/phonemic inventory as well. If all of your words have CV or CVC syllables, then it's going to be easy to find minimal pairs. If you allow CCVCCC, it's going to be harder. The fewer syllable types, the more languages are going to have to depend (so to speak) on words that are only minimally different.
I've experienced this personally: in an Iranian language I studied it was impossible or almost impossible to get minimal pairs for a contrast that was clearly phonemic, based on native speaker intuitions. And there were very few minimal pairs of any sort. On the other hand, in a Turkic language, I run into minimal pairs constantly, without even having to think about it.
You don't need to have minimal pairs that contrasts all phonemes with the others.
Phonemes are bundles of articulatory or phonetic features. If you have a pair that opposes p to t, and a pair that opposes t to d, and a pair for p vs b, then you don't need a pair for b vs d, because you already showed that labial is not dental, and voiceless is not voiced.