Antagonistic coevolution between hosts and parasites is known to affect selection on recombination in hosts. The Red Queen Hypothesis (RQH) posits that genetic shuffling is beneficial for hosts because it quickly creates resistant genotypes. Indeed, a large body of theoretical studies have shown that for many models of the genetic interaction between host and parasite, the coevolutionary dynamics of hosts and parasites generate selection for recombination or sexual reproduction. Here we investigate models in which the effect of the host on the parasite (and vice versa) depend approximately multiplicatively on the number of matched alleles. Contrary to expectation, these models generate a dynamical behavior that strongly selects against recombination/sex. We investigate this atypical behavior analytically and numerically. Specifically we show that two complementary equilibria are responsible for generating strong linkage disequilibria of opposite sign, which in turn causes strong selection against sex. The biological relevance of this finding stems from the fact that these phenomena can also be observed if hosts are attacked by two parasites that affect host fitness independently. Hence the role of the Red Queen Hypothesis in natural host parasite systems where infection by multiple parasites is the rule rather than the exception needs to be reevaluated.