Judging by dictionaries and grammars, we seem to know the length of almost every vowel in classical Latin. For word-final vowels and those followed by a single consonant, the length can be figured out from metric poetry. Not all words can be found in all forms in extant poetry, but the corpus is large enough to establish a significant portion of all vowel quantities. But if there are more than one consonants after the vowel, the syllable is always long — or heavy if you prefer that nomenclature — and the length of the vowel itself is metrically irrelevant. How do we know the lengths of such vowels?
The length of vowels with “hidden quantity” can often be discovered from one of the following sources of information:
Explicit descriptions of vowel length in ancient texts
“Lachmann’s law” is a well-known rule about the length of vowels in closed syllables in past participles; we have a description of this from the works of Aulus Gellius according to William Sidney Allen in Vox Latina (68). Allen's entry on Lachmann's Law also discusses various other types of evidence for vowel quality in this context, so I’ll reference it a few more times in this answer.
Sources of Uncertainty: We don’t know how accurate ancient writers were at formulating accurate descriptions of rules for vowel length. In some cases, there may be uncertainty about how to interpret the words used in ancient descriptions of pronunciation. Nonetheless, this is an important source of information.
Use of apex, i longa and other devices in ancient inscriptions
These are described in "The Use of Devices for Indicating Vowel Length in Latin," by John C. Rolfe, Ph.D., read April 20, 1922.
The modern scholar, in spite of the silence of the native grammarians, might be led to inquire whether the so‑called "hidden quantities" are designated by marks. We find that in the M. A. [Monumentum Ancyranum] twenty-six such vowels are marked, but they amount to only about 20 per cent of the 138 hidden quantities in the whole inscription. (87-88)
This text also briefly mentions another device used earlier on to mark long ī: the digraph ei (83-84). This spelling convention arose due to sound changes between Old Latin to Classical Latin. There are other Old Latin digraphs that correspond to long vowels in Classical Latin, such as ou (which corresponds to long ū). Wikipedia and Rolfe (83) say that Old Latin inscriptions may also indicate long vowels by doubling the vowel; Wikipedia gives the example of "aara for āra."
Notable limitations: As the quotation says, genuinely long vowels were not consistently marked with these devices. So it’s hard to get good evidence from this source for a vowel being short.
Sources of Uncertainty: It seems that in some cases, the i longa was used on short vowels to indicate something other than vowel length (possibly “emphasis” or “dignity”). Both Rolfe (86, 91) and Allen (70) mention this.
Vowel length in descendants
We can look at the vowel quality of descedant words in Romance langs: many of them have distinct reflexes of long and short vowels. For example, Allen contrasts French doit, from Latin dirēctum, and dépit, from Latin despĕctum (70).
Notable limitations: Not all Classical Latin words have attested descendents in a Romance language. As far as I know, long and short “a” do not have different reflexes in any Romance language.
Sources of uncertainty: Romance may reflect post-classical variation in vowel length (i.e. the length of a vowel in Proto-Romance may differ from the length in Classical Latin); words may show language-specific effects of analogy/restructuring. Allen mentions “dictus” shows inconsistent reflexes in Romance: Italian has detto (pointing to a short vowel) while French has dit (pointing to a long vowel) (70).
Vowel length in related Latin words, cognates
We can look other Latin words that seem related for which we know the quantity. We can also look at words in related Indo-European languages (such as Greek or Sanskrit) that might have clearer indications of the historical vowel length. (I can't think of an example of this, sorry.)
Sources of uncertainty: Sometimes the etymology of a term is unclear. It’s also possible that that the length of the vowel in one or both of the languages was affected by some unknown sound change or analogical process, or by the process of ablaut which could cause roots to have multiple forms with different vowel quantities already in Proto-Indo-European.
I only listed "sources of uncertainty" to try to be reserved about what we know. I think that in most cases, the quantity of a vowel is known fairly well because we have several different sources that agree with each other. A good dictionary should indicate any areas of true uncertainty by some method like not marking length on the vowel, marking it with both a macron and a breve, or including a discussion of the pronunciation. In my experience, I feel references have misled me about hidden quantity in only a few cases, each time by the use of macrons, since macrons are unfortunately ambiguous between indicating vowel length or syllable length. The examples I can think of are: far (which Lewis transcribes as "fār"; Charles Edwin Bennett says it was the final consonant, not the vowel that was long) and major (which Lewis and Short transcribe as "mājor"; Allen says the "a" was short and the "j" was long). It may also be relevant that neither of these has two written consonants after the vowel, so the dictionary authors might have felt a macron on the vowel was the only option for indicating that the syllable was heavy.