Eccoti la mia opinione spassionata:
I link sono importantissimi per il rank nei motori e su google in particolare, però non credere che raccattare link a destra e a manca ti possa aiutare comunque... può darsi che un link da una pagina a pr basso, provieniente però da un sito a tema col tuo, magari "trusted" possa darti più spinta di un link a pr più alto, ma da una pagina che non c'entra un bel nulla.
Secondo me per quanto riguarda il posizionamento non fa poi tutta questa differenza... è più un fatto di immagine, di brand, di come ti vuoi presentare all'utente... e soprattutto di quanto vuoi spendere, specie se prevedi di espanderti oltre le due città!
Mi è capitato di vedere ultimamente dei network di siti turistici che usavano il modello dei domini differenti, ognuno per una nazione... può darsi che comunque sia un sistema che funzioni quello. Nelle directory ce li puoi mettere comunque in entrambi i casi!
Directory a pagamento: secondo me alcune possono aiutarti a spingerti, se sono a tema, se il link è ben piazzato, ecc. Forse però in inglese per siti italiani non ne vale la pena... sicuramente non linkerei quando il sito è giovane.