I have noticed that these two words have a similar meaning, such as "agreement" or "accord." But it seems that they are often not interchangeable because they "get there" in different ways. Is this true, especially given the context of politics?
To get a better understanding of the two words, let us look at the corresponding verbs:
(etw.) vereinbaren = to agree, to contract sth., to arrange, to appoint
übereinstimmen = to correspond, to accord, to coincide, to match
Knowing this we can easily see the difference between the two nouns:
die Vereinbarung = the agreement, the arrangement, the contract
die Übereinstimmung = the accordance, the accord, the compliance, the agreement
One could go into more detail, but I think when seeing the nouns as nominalization of its corresponding verbs, the difference already gets clear.