One thing to recognize, is that borders have traditionally been much fuzzier than they are now. In days of the Polish-Lithuanian empire, for instance, you'd have towns that considered themselves German, with ties to the old Holy Roman Empire. And these towns, even though they might be surrounded by the lands of Polish lords, wouldn't necessarily maintain fealty to the Polish king. In a lot of ways, you could even have two or three different, overlapping "territorial" claims within the same geographic space, without having an inherent conflict.
