Our analysis underscores the reality that respiratory viruses are difficult to detect by symptom and risk screening programs, particularly if a substantial fraction of infected people show mild or indistinct symptoms, if incubation periods are long, and if transmission is possible before the onset of symptoms. Quantitative estimates of screening effectiveness for COVID-19 will improve as more is learned about this recently-emerged virus, and will vary with the precise design of screening programs. However, we present a robust qualitative finding: in any situation where there is widespread epidemic transmission in source populations from which travellers are drawn, travel screening programs can slow (marginally) but not stop the importation of infected cases. Screening programs implemented in other settings will face the same challenges. By decomposing the factors leading to success or failure of screening efforts, our work supports decision-making about program design, and highlights key questions for further research. We hope that these insights may help to mitigate the global impacts of COVID-19 by guiding effective decision-making in both high- and low-resource countries, and may contribute to prospective improvements in screening policy for future emerging infections.