Bacteriophages-or phages-are viruses that infect bacteria and are present in large concentrations in the mucosa that cover the internal organs of animals. Immunoglobulin (Ig) domains on the phage surface interact with mucin molecules, and this has been attributed to an increase in the encounter rates of phage with bacteria in mucus. However, the physical mechanism behind this phenomenon remains unclear. A continuous time random walk (CTRW) model simulating the diffusion due to mucin-T4 phage interactions was developed and calibrated to empirical data. A Langevin stochastic method for Escherichia coli (E. coli) run-and-tumble motility was combined with the phage CTRW model to describe phage-bacteria encounter rates in mucus for different mucus concentrations. Contrary to previous theoretical analyses, the emergent subdiffusion of T4 in mucus did not enhance the encounter rate of T4 against bacteria. Instead, for static E. coli, the diffusive T4 mutant lacking Ig domains outperformed the subdiffusive T4 wild type. E. coli's motility dominated the encounter rates with both phage types in mucus. It is proposed, that the local fluid-flow generated by E. coli's motility combined with T4 interacting with mucins may be the mechanism for increasing the encounter rates between the T4 phage and E. coli bacteria.