I'm curious what sources you are citing for the prevalence of independent cities. In all cases I can think of the independence is part of a multinational agreement, a coalition of independent but allied city states, or on par with the other power players in the region.
In any case, all of those arrangements should be possible in Elyria, provided conditions are right. Let's look at each:
Multinational Agreement:
Though highly unlikely to develop before launch (and certainly impossible before land selection), it could come to pass that several political bodies decide to accept the neutrality and independence of an importantly positioned city and may chose to recognize its independence, exempting it from local laws. This would require an incredible amount of trust, or a fantastical amount of leverage to establish.
Coalition of City States:
This sort of thing is already happening at the county level with groups like the Order of IX. On the small scale, if a group of settlements were able to challenge the authority of their count they would be able to win free of county laws, but would still be subject to the duchy and kingdom. Essentially, any such alliance will only have weight to subvert the authority of the tier above them--and really only by installing a figurehead in the executive position who agrees to let all parties stay independent. Any further than that would require the same immense leverage or trust as in the previous example.
Independence Among Peers:
To become truly independent from all forms of greater authority, one must be able to match all challengers to that independence. That is in essence what a Kingdom is, and imperfectly so--as we know not all Kingdoms will be equivalent in power. If a mayor were to gain enough power to win independence from her county she would become a count of her own small county. She would then need to expand her borders enough such that three counties worth of land were hers in order to secede and make her own duchy. But let's say she wants to continue to keep her county-sized city, and simply plans to cut herself off from duchy and kingdom taxes and law. Again, this independence will require trust, leverage or might to preserve. Our mayor-count will need to fend off siege after siege from the thousands of troops at the command of the local duke and king until both grow weary of trying. Even then, she will likely starve or become bankrupt unless she can convince the surrounding authorities to trade with her. The chances of this being sustainable are miniscule unless you happen to house all of the most talented PvP players and most effective smugglers in the game.