This happened to me once too! I was conquering Scythia and Campus Getae had plague. I inadvertantly walked my conuqerors into the infested city, the enemy spy popped out, then promptly disappeared and began infecting other armies and cities. He only got two of my generals I think, but they were good generals, and it was in the middle of nowhere, so it took a long time to get more into the area!

That darn spy! By the time I got my own spies and assassins into the area, he was long gone (I hope the bugger died horribly of the plague).

Others have mentioned using an infected spy to afflict the enemy, though one would never figure the AI would use it. Stupid AI...