Como vc já viu é complicado e a regra também é complicada, depende do conhecimento do uso da língua. Se o local aceita artigo "o" ou "a" então a preposição "de" vai de fundir com o artigo. "De" + "a" = da. "De" + "o" = do. Se não se usa o artigo a preposição fica sozinha. "De". Mas, como saber se o comum é aceitar, ou não o artigo? Só o tempo lhe dará está prática. Por exemplo ninguém fala "O Portugal", ou "A Portugal". Então fica só a preposição. "De Portugal. Já "A Espanha" todo mundo fala. Então "Da Espanha". "O Japão", fica "Do Japão". Tem alguns casos em que se pode falar com o artigo, mas não é comum o seu uso. Normalmente só se usa o artigo quando se quer especificar uma época um acontecimento. "A São Paulo dos modernistas", "A Paris da Belle Époque". Fora isto se fala São Paulo e Paris. Então a preposição fica sem o artigo. "De São Paulo" e "De Paris" A regra é mais complicada ainda. Eu fiz um resumo. Não se preocupe muito com isto. Só o tempo lhe ensinará. Quando não souber arrisque. Masculino "Rio de Janeiro" use "do", feminino França usa "da". Indefinido "Berlim" use "de". Quando você errar como em Canadá que é "do" todos vão entender que vou concordou com o gênero masculino/feminino

http://www.easyportuguese.com/portuguese-lessons/prepositions/ maybe help you.

There no specific rule. It's just a matter of tradition, usage. Some of them are usually written with an article before (de+o = do, de+ a =da), because they're associated with masculine or feminine articles ("o" or "a", respectively) , whereas the others are used without an article before (just "de"), because they are not commonly associated with a gender (of course, there are exceptions, like "Série de fotos impressionante mostra *a* Nova York dos anos 70 e 80" and so on, but I'd say "Eu vim *de* Nova Iorque") . Concerning your suggestion: for instance, let's say"Ele veio..." (de)Paris,(de) Londres, (de)Nova York, (de)Berlim, (de)Tóquio, (da)Espanha,(do) México, (da)França, (do)Canadá, (de) Roma, (de)Portugal,(do) Rio de Janeiro.

If the name of the city / town / village coincide with a common name (eg: Porto - name of a city - and port - common name), takes the definite article the common name ("Porto" and "the port "), which implies the occurrence of the definite article expressions with prepositions de, em, a [contractions (do= de + o; no= em + o; ao=a + o)]. Ex: Eu sou do Porto. Eu sou de Lisboa Portugal and most Portuguese-speaking countries which were formerly part of the Portuguese Empire, with the exception of Brazil and Guiné-Bissau, do not take the definite article (Portugal, Cabo Verde, São Tomé e Príncipe, Angola, Macau, Moçambique, Timor) and certain other countries do not take the definite article, like: Marrocos, Israel, Andorra. Ex: Eu sou de Portugal. Eu sou do Brasil (masc)

Eu não sei se tem regra, aprendi ouvindo pessoas a minha volta falando assim. Sou de Paris De Londres De nova iorque De Berlim Da Espanha De Tóquio Do México Da França Do Canadá De Roma De Portugal Do Rio de Janeiro