From what I read on the forum so far, it seems to be mostly a problem with missions that give a large number of claims at once. The opinion modifier doesn't know that all those claims disappear as soon as any one claimed province is owned, it's calculated as if every one were needed.
This could be avoided by giving claims an attribute, opinion_weight or so, which controls how much this claim contributes to the "Wants your provinces" opinion modifier, with a default value of 1. The mission that gives x claims at once could then set each claim's weight to 1/x, so the "love" gets evenly spread out over the owners of the claimed provinces, with a sum of 1 province's worth of "want".
Another way might be not to change the "Wants your provinces" modifier instantly, but letting it slowly shift to the target value, with speed depending on attitude. E.g., if AI gets the spice mission, the target value for Wants... becomes -200, but if their attitude is Friendly towards you, it decreases only by, say, 5 per month. This would give the AI a chance to get their province before breaking off alliances, and the player might notice in time to take action (e.g., selling them a fricken province, if need be). If the attitude is Hostile, Rival, etc., the opinion modifier may as well drop all the way instantly. This would make the AI somewhat more lenient towards it allies, but eventually grow impatient about getting its claims, which would seem more-or-less plausible.