For most pathogens, vaccination reduces the spread of the infection and total number of cases; thus, public policy usually advocates maximizing vaccination coverage. We use simple mathematical models to explore how this may be different for pathogens, such as influenza, which exhibit strain variation. Our models predict that the total number of seasonal influenza infections is minimized at an intermediate (rather than maximal) level of vaccination, and, somewhat counter-intuitively, further increasing the level of the vaccination coverage may lead to higher number of influenza infections and be detrimental to the public interest. This arises due to the combined effects of: competition between multiple co-circulating strains; limited breadth of protection afforded by the vaccine; and short-term strain-transcending immunity following natural infection. The study highlights the need for better quantification of the components of vaccine efficacy and longevity of strain-transcending cross-immunity in order to generate nuanced recommendations for influenza vaccine coverage levels.