I find that withdrawing an re-initiating an embassy with someone else fixes that (say, withdraw your embassy with Kedeshi, and you'll end up with two free embassies, then immediately re-establish the Kedeshi embassy). But yes, I've had this happen (also when having an embassy with a nation that is swallowed up in a war).