En l’occurrence, comme il s’agit de définir un type particulier de nom, une catégorie, il ne faut pas mettre d’article devant villes.
C’est à rapprocher des exemples que le site d’où est extrait cette phrase donne : chien de berger vs chien du berger  / table de jardin vs table du jardin.
Donc noms de villes, noms d’animaux, noms de pays = catégorie de noms  >>> pas d’article devant le complément du nom (qui est utilisé comme un adjectif).

Vous avez ici (et là) un point détaillé sur cette question. En gros, c’est mieux sans ce ne – qui ne peut être qu’explétif -, mais ce n’est pas faux avec (le degré de tolérance variant selon les époques ou selon les grammairiens).

Le Tlfi le donne peu usuel, sans plus de précisions :

Vous dites : « Cela me parait correct, mais je lis que « il y a que » a le sens de « depuis »… ». Oui, c’est un peu plus compliqué que ça, parfois il y a équivalence entre il y a que et depuis, et parfois non, parfois l’un et ou l’autre fonctionne avec le présent et/ou le pc, parfois non. Je vous donne une série d’exemples qui illustrent les différents cas de figure (j’ai rajouté la forme il y a (sans que), ça aide à analyser), et je vous laisse en tirer les conclusions  :

Habiter + présent
Il y a dix ans / 2013 / Noël / le 25 décembre que j’habite à Paris.
Il y a dix ans, j’habite à Paris.
J’habite à Paris depuis dix ans / 2013 / Noël / le 25 décembre.
Habiter + PC
Il y a dix ans que j’ai habité à Paris.
Il y a dix ans, j’ai habité à Paris.
J’ai habité à Paris depuis dix ans.

Quitter + présent
Il y a dix ans que je quitte Paris.
 ?Il y a dix ans, je quitte Paris.
Je quitte Paris depuis dix ans.
Quitter + PC
Il y a dix ans / 2013 / Noël / le 25 décembre que j’ai quitté Paris.
Il y a dix ans, j’ai quitté Paris.
J’ai quitté Paris depuis dix ans / 2013 / Noël / le 25 décembre.

Venir + présent
Il y a dix ans / 2013 / Noël / le 25 décembre que je viens à Paris.
Il y a dix ans, je viens à Paris.*
Je viens à Paris depuis dix ans / 2013 / Noël / le 25 décembre.
Venir + PC
Il y a dix ans que je suis venu à Paris.
Il y a dix ans, je suis venu à Paris.
Je suis venu à Paris depuis dix ans.

Si vous n’arrivez pas à débrouiller cet écheveau, je vous donnerai la solution (en tout cas des pistes).

*Pourrait fonctionner avec une suite, où le présent aurait valeur narrative : Il y a dix ans, je viens en toute urgence à Paris pour célébrer son anniversaire, que j’avais complètement oublié, goujat oublieux que je suis !

Les traits d’union ne valent que pour le substantif, ici nous ne sommes pas en présence du substantif, mais d’une locution adverbiale en fonction adjectivale, donc :
C’est un pays hors la loi / Il est hors la loi.
Cet homme est un hors-la-loi.

Je ne perçois pas la nuance indiquée par Bruno, qui par ailleurs n’est pas pertinente en l’espèce, puisque l’énoncé est hypothétique, par conséquent la besogne n’a pas été réalisée / les contraintes n’ont pas été supprimées ou surmontées (en tout cas au moment de l’énonciation).

Personnellement, j’y vois moins une nuance de sens, que de registre : en dépit de est plus soutenu que malgré.

L’analyse de ce de est compliquée et ne fait pas l’unanimité, néanmoins je pense qu’il sera actuellement plutôt analysé comme un partitif (c’est le cas du Tlfi – voir ci-dessous-, de Grevisse, de Wilmet, entre autres).

Rem. L’art. prend la forme de a) après une loc. adv. de quantité indéf. Peu de, un peu de, beaucoup de. Verse-moi un peu de sherry (H. Bataille, Maman Colibri, 1904, I, 2, p. 3).

Peu importe que le nom soit concret ou abstrait, ce qui importe, c’est qu’il soit non comptable (pour ces derniers, c’est le quantifieur quelques qui convient) :
Je veux du pain / du silence / de la tranquillité / des chaises >>> Je veux un peu de pain / un peu de silence / un peu de tranquillité / un peu de chaises / quelques chaises.

Cette question des articles devant le NOM2 dans les structures du type NOM1 de NOM2 est un point très complexe. Si vous n’êtes pas Français, il vous sera très difficile de savoir quel article mettre. Pour en rester aux deux exemples que vous donnez :

Salle des fêtes = salle qui est utilisée pour organiser les fêtes (du village, du quartier,…) >>> préposition de + les —> des.
Salle de fêtes = salle qui est utilisée pour organiser des fêtes >>> préposition de + des —> de.
Salle de fête = salle dédié à la fête >>> préposition de + pas d’article —> de.
Dans le dernier cas, l’absence d’article devant le mot fête lui donne une valeur quasiment adjectivale : salle de fête ≃ salle festive. Si on mettait un article (salle de la fête), ça voudrait dire que c’est la salle d’une seule fête bien définie, ça n’a pas de sens.

Dans le cas présent, l’usage retient ces quatre possibilités (même si certaines sont moins usitées que d’autres) – salle des fêtes / salle de fêtes / salle de fête / salle festive – pour désigner la même chose.

Bureau d’études = bureau où on réalise des études/expertises >>> préposition de + des —> de.
Bureau des études = bureau où on réalise les études (commandées par les clients / nécessaires à l’entreprise) >>> préposition de + les —> des
Bureau d’étude = bureau spécialisé dans l’étude / l’expertise >>> préposition de + pas d’article —> de (pour les mêmes raisons que salle de la fête, l’article n’est pas possible avec le singulier).

Là encore l’usage retient les trois possibilités, bien que les deux dernières soient très nettement moins usitées que la première.

Pour reprendre un des exemples donnés par Bruno, salle + sport, on peut aussi bien avoir : salle des sports, que salle de sports ou encore salle de sport, voire salle sportive.

Il est des cas où une ou plusieurs possibilités sont rejetées (bien qu’elles soient possibles dans l’absolu), ainsi par exemple dit-on code de commerce, éventuellement code commercial, mais pas code du commerce. A contrario, on dit code du travail et non code de travail.

à trois pas du poêle est le complément du participe arrêté (ici en fonction adjectivale).
sous le bras est complément du nom (du syntagme nominal) petit paquet.
et oui pour en beau plâtre blanc, c’est bien un cdn du buste du roi.

À mon avis, ce qui pose ici problème, c’est moins apte (qui peut s’utiliser également pour les inanimés – en passant les fruits ne sont-ils pas des animés ?) que affronter. Ce terme contient la notion de courage, et si un fruit est certainement un être vivant (pour les botanistes, biologistes, ça ne fait aucun doute, pour les grammairiens peut-être que si), il est peu probable qu’il ait du courage, donc sauf à faire de la poésie, de la littérature et à prêter ce type de propriété à un fruit, je pense qu’il vaudrait mieux opter pour un autre verbe.

Apparemment colonie de Madagascar et (ses) dépendances est le nom d’une entité (comme par exemple Wallis-et-Futuna ou Saint-Pierre-et-Miquelon – évidemment dans ces deux cas et contrairement à celui qui nous occupe, la présence de traits d’union rend manifeste la désignation d’une entité unique), par conséquent le verbe qui suit doit normalement être au singulier, mais il faudrait avoir la phrase entière pour pouvoir décider. Ainsi, en reprenant un des deux autres cas, on pourrait aussi bien avoir un singulier qu’un pluriel (sauf que là encore la présence des traits d’union facilite les choses) :

Saint-Pierre-et-Miquelon est un archipel français / Saint-Pierre et Miquelon sont deux îles situées dans l’océan atlantique.

Edit
À la réflexion, il est possible que le petit ses joue le même rôle que les traits d’union dans Saint-Pierre-et-Miquelon / Saint-Pierre et Miquelon, autrement dit, il se pourrait bien que l’entité soit dénommée colonie de Madagascar et dépendances (obligatoirement sans déterminant devant dépendances), auquel cas le verbe qui suit se met forcément au singulier, et que l’introduction du possessif casse l’entité et qu’il faille alors entendre les deux membres de la coordination comme indépendants et référant par conséquent à deux entités distinctes, auquel cas le verbe qui suit est forcément au pluriel.