I was allied with the HRE. They set out a crusade against Palestine. They parked themselves in Venice. I figured I'd beat them to the punch, in hopes of taking the province before them.

So, I attacked the Egyptians. I worked my way down the Med. coast. I also decided to do an amphibious landing in Egypt, to head off any adventurism by the Almohads. Of course, that meant defeating the Egyptian fleet.... (Actually, thinking back, I was already at war with the Egyptians. I took several provinces, before the HRE started their crusade...)

So, I killed off the Egyptian fleet. Next turn, the HRE crusade jumped from Venice to Palestine. Yep, as I was at war with the Egyptians, my fleet was blockaded. As soon as the way was clear, the HRE bypassed my armies in Serbia, Bulgaria and/or Greece, Constantinople, and so on down to Palestine.

So, maybe the computer's pathfinding had determined that my extensive trade network of ships was the quickest way to Palestine, and waited in Venice until I so nicely cleared the way for them....