Actually that's not true, bacteria only has a limited amount of space for genes. And the more gene's they have the more ways there are to kill them. There will always be a way to destroy a type of virus.
Quick note... Bacteria != Virus.
Viruses actually have less genes in them than a bacteria (not sure if there are any complex viruses with more than the simplest bacteria, without going back to some old books or wiki, but
in general this should still be the case), because they make use of the genetic material of the cells they typically infect to do most of the complex stuff like setting up the replication pathways, so they need not so much of it themselves). This is also means that viruses are very capable of soaking up mutations, because, unlike "full blown" cellular life, they aren't (as) susceptible to mutations happening to the reproductive mechanisms (something else is doing it for them!) and, like-as-not, stopping there from being a next generation.
As long as a virus is actually tricking the cell to put its genetic code copying machinary into play, encapsulating it in a suitable membrane and then get those encapsulations spread (e.g. by getting the cell to kill itself and disperse its contents), viruses don't really care what new coating they will have. If it doesn't latch onto other cells, then obviously it fails, but as long as it isn't destroyed by environment or a primed immune-system it can probably sit around until it
does find itself latching onto something that its protein coat likes. Unlike a proper cell, it doesn't have to sustain itself in the same way. (And even 'proper' forms of life can be universally hardy, look at tardigrades, etc as creatures that aren't just extremeophiles but able to survive handle a wide range of environments, albeit in something akin to a form of chemical 'stasis'.)
Anyway, the point is that there's less genes to aim at (by the quoted logic, less ways to kill them, although I'm not sure that it's quite as proportional) plus the genes (or at least genetic sequences) are really quite malleable and moving targets are harder to hit.