Why? Yes, it's possible and it has a name: Belgium. Of course, joke aside, it's still one country with a single federal government so not really an international condominium as far as international law is concerned but the architecture of its political system is very unusual and seems relevant to your question.
I am not a specialist but I will try a brief description of (what I understand about) how this works. There are two types of federated entities (“regions” and linguistic “communities”) and every place in Belgium belongs to at least two of them and the Brussels area belongs to three (it's a region in its own rights and belongs to both the Flemish and the French-speaking communities). Their norms are deemed “equipollent” with no clear priority between the two sets of entities and the federal level.
These “communities” are not merely representative bodies with a symbolic or cultural role, they have their own government, their own budget, some (limited) powers of taxation. And they run important services, like education. The number of civil servants working for the Fédération Wallonie-Bruxelles (the French-speaking community) and the number of those working for the Service public de Wallonie (the region) are roughly on the same order of magnitude (that's without counting all the teachers whose wages are also funded by the community).
Of course, there are a few differences with your scenario: Instead of a single well-defined entity that belongs to two separate countries, you have different overlapping entities that ultimately belong to the same country. And there is a single constitution and a constitutional court. But the very unusual (and to my mind very relevant) thing is that just as in your fictional federation(s), you have two (or three) sets of norms, in principle without any clear hierarchy between them that apply to the same territory.
It kind of works, too. I know many people who have bad things to say about Belgium but obviously it's still a relatively rich and modern country and hasn't descended into complete anarchy.
One reason for that is that broadly speaking, communities and regions are in charge of different things (say the regions are in charge of roads, the communities of schools and the federal state of the army), which removes much of the potential for conflict. As in your example, being part of the European Union probably helps as well because many things have been offloaded “upwards” from the federal level to the EU, further reducing its role and the potential for conflict between the parallel structures of government.