The Pope tends to tolerate small Catholic Factions attacking large ones, but not the other way round. This is indeed carried to the point of madness when it comes to reconquering lost ground or attacking in sea battles, but there it is. It is not the only way the computer cheats.

However, I have never seen cheating naval invasions. I don't know how BKB's map looks, but if it is like the vanilla M:TW map, one ship in the Gulf of Lions ought to have prevented it. They could have used a line of ships along North-Africa to invade.