I think the same, when I try to kill the pope because he excomunate me, I remember have seen an advice on the screen that combinated plot is most likely to succeed, maybe if you launch your spy/assasin attack from different provinces. It work perfectly, I send 5 assasin from three different province, two were catch but one succeed and finally it cost me 3 assasin (one more died next turn, when trying to escape)