perhaps this can explain it... or confirm it.
When I was playing at a mates place, I had the same happen on his game.. which highlights 3 issues(probably bugs)
We had vassalised ethiopia and completely taken over all the cities of spain and russia. We had taken over all but 3 of ethiopias cities when we ran out of men and offered to vasslised him...
Issue 1
OVer the remainder of the game, we would be prompted sometimes to liberate our cities to him which we refused.... however the game would automatically liberate so much that eventually he not only controlled all his old cities however he also have automattically liberated 3 former russian cities that I had conqueired... Some with huge culture and wonders..... So he had automatically "liberated" cities that were never his..
Issue 2:
I had captured a barbarian city on the far side of his empire, after I had vassalised him, howver I was prompted to capture, raze, or "return it to ethiopian control" (It was a former barbarian colony.) which I refused.. however I was repeatedly prompted to liberate it to the ethiopians.
Issue 3:
After that I built a colonisation fleet to colonise the islands on the otherside of my empire to the ethiopians. After I had built about 4 or 5 cities on the islands, I was prompted to "liberate the colonies to ethiopia." These colonies were colonies that I had created, and had never been part of ethiopia.... Also when I went to try give colonial status, I was prompted to liberate to Ethiopia! Anyway after sometime I was able to finall not libereate but grant it independence.
Summary,
It seems that once you have vassalised someone, the game has difficulty distinguishing between cities that were formerly his, and cities that were formerly of any conquered civilization...
In addition it seems that it might be something wrong with the city ownership system as it identifies new cities near the vassals and cities away from the vassal as being "formerly vassals"
In addition this "liberation creep" became so bad that the vassal, was the rival in UN leadership and won using our former cities..... (why didn't the vassal vote for us??)
Am going to play on my computer to see if it is just on his settings... ( i think he chose default game with big continents map on Chieftain)