Numerous Australian terrestrial orchid species in the genus Diuris may be pollinated by food source mimicry. In our field studies, direct observations of orchid–pollinator interactions were rare, but native bees were frequently captured carrying orchid pollinaria, or pollinaria remnants. Sometimes, pollinaria remnants were minimal and included only the viscidium, a sticky pad that was often highly persistent. Confirmation of such tissue as being of orchid source, and attributing them to a particular species can aid pollination studies. DNA-based methods that may identify more or less intact orchid pollinaria are available, but extremely small and degraded samples can pose technical challenges. We have developed an AFLP protocol for such difficult samples that offers some significant advantages over direct PCR-based analysis. We simulated AFLP profiling of very low-DNA samples using DNA template from serial dilutions. A DNA sample range from 6.4 picograms to at least as high as 100 nanograms (15 500-fold range) all yielded AFLP fingerprints. The practical application of this inherent sensitivity of AFLP is demonstrated by the identification of remnants of orchid pollinaria sampled from bees, presented here as a case study. It is expected that this approach will find many applications where sample DNA is limiting, or possibly where pollen of similar appearance may comprise species mixtures.