Diolch @garethrking! I remember looking this up in Colloquial Welsh a while back, where the example is "the bike of the girl", but what I apparently didn't understand is that this pattern covers all eventualities. I remember thinking, well, what about "a girl's bike" = "a bike of a girl" (I saw a girl's bike by the side of the road - I knew it belonged to a girl because it was pink...).
Your set of examples is really helpful, especially the last two. I wouldn't have understood that the "the" in "the Netherlands" counted as the last "the" for the pattern, because I would have pegged is as just part of the name. And I would have thought it was the "the army" part of "the leader of the army of Costa Rica" that was important. So thanks very much for that!
So it looks like (as a not very good example, imagining that there are multiple armies in Costa Rica with multiple leaders)
a leader of an army of Costa Rica = arweinydd byddin Costa Rica
would have to be distinguished by context from
the leader of the army of Costa Rica - arweinydd byddin Costa Rica
since they are the same.
Also, my radar being set to find examples, last night I was listening to music and picked out the line
ond pan ddaw haul y bore
from Angel by Elin Fllur. This is one where I wouldn't have thought of "the sun of the morning" but would have just thought of morning as an adjective and said "haul bore". I just need to keep looking out for the pattern and learning by exposure...