J’avoue que je n’avais jamais fait attention à cette règle (je réalise du même coup que pour un étranger apprenant le français ce genre de distinction doit être un caprice linguistique un peu épineux), mais ne serait-ce que pour comparer nos considérations euphoniques, je les classerais comme ceci :

(en gras ce qui me parait euphonique, en italique ce qui me choque/gêne)

Je viens de l’Allemagne | Je viens d’Allemagne

Je viens de l’Inde | Je viens d’Inde

Je viens de l’Uruguay | Je viens d’Uruguay

Je viens du Canada | Je viens de Canada

Je viens de l’Andalousie | Je viens d’Andalousie

Je viens de l’Afrique | Je viens d’Afrique

Personnellement, cependant, je n’ai pas d’exemple de nom de pays commençant par une voyelle qui me semble échapper à la règle. A part la répétition éventuelle du son d que tu mentionnes, effectivement, mais qui ne me semble pas assez gênante pour empêcher l’emploi des expressions Je viens d’Inde ou Je viens d’Odessa.

Mais peut-être ne voulais-tu pas ce genre de réponse assez subjective ?

C’est peut-être un problème d’humour :

Je reviens d’Inde, en jouant avec les mots peut s’entendre : je deviens dinde, donc le l’ s’impose pour empêcher cette possibilité.

De même avec Perse et le verbe percer.

Il y a aussi le phénomène d’apprentissage : qu’un enfant me dise tu viens de l’Italie ?, ne me choque pas, pour deux raisons :

• Il respecte scrupuleusement la construction primitive des phrases
• L’Italie peut être, pour lui, un pays éloigné, imaginaire, merveilleux.

Mais je tiquerais un peu sur l’ironie sous-jacentes de cette même phrase employée par un ami lettré.

En effet, Jean Bastin pointe la notoriété du pays cité : si l’on s’efforce de préciser par le, la, l’ c’est que l’on suppose que la personne à qui l’on parle ne sais pas où se situe ce pays, ou qu’il est rarement mentionné dans les médias.

---

Complément

Je viens d’Allemagne .

L’entité, ici le pays, l’identité nationale est l’Allemagne

Je viens de l’Allemagne du nord .

On indique une région de l’Allemagne, l’Allemagne englobant de nombreuses zones géographiques.

Charles Trenet ne chante pas “Douce la France / Cher pays de mon enfance / …”, car il parle du pays cher à son cœur, pays partagé par tous les Français.
Mais on pourrait chanter “La France que j’aime se trouve dans ton regard”, car il s’agit d’une image singulière de la France, image liée à une histoire particulière.

Je ressens une différence.

“Je vis à Paris, mais je viens d’Allemagne” = j’en suis originaire.

“Mes vacances sont finies, je (re)viens d’Allemagne”.

Bon, je tente ma chance.

Selon le contexte donné, selon moi :

« d’Allemagne » est généralement à utiliser lorsqu’il s’agit, par exemple, du notre pays d’origine.

Tandis que « de l’Allemagne » serait quant à lui plus “temporaire”.
Comme par exemple « Je (re)viens de l’Allemagne (par exemple, j’y suis allé ce matin) » même si je pense qu’utiliser « d’Allemagne » dans ce cas ne serait pas totalement faux non plus.

Pour répondre à l’exemple « je viens de la Russie Profonde » :
Généralement on utilise pas le “la” lorsqu’il s’agit d’un pays, ainsi il serait plus correct de dire « je viens de Russie » plutôt que « je viens de la Russie » par exemple.
Mais dans ce cas précis, on ne parle pas “juste” de la Russie donc il semble plus correct de dire « je viens de la Russie Profonde » plutôt que de dire « je viens de Russie Profonde » cela sonne faux, car, selon moi, ce n’est pas l’appellation officielle d’un pays.

Enfin, je pense que l’article est plus souvent utilisé pour décrire l’objet (par exemple lorsque je parle de LA Russie) et plus souvent omis pour désigner une origine (« je viens d’Italie »).

Cette distribution étrange est récurrente en français. Elle apparaît de la même façon pour au et en avec les mêmes types de noms de pays (et noms propres de lieux). On utilise, au singulier, en devant tous les féminins (en France, en Italie) et les masculins qui déclenchent l’élision (en Iran), et au devant les masculins qui ne déclenchent pas la liaison (au Portugal). Cette différence est neutralisée au pluriel avec la présence généralisée de aux.

Ce phénomène est à rapprocher de la distribution des possessifs et des démonstratifs singuliers :

• mon, ton, son apparaissent avec les noms masculins (mon chat, mon oiseau) ou avec un nom féminin devant un mot qui déclenche la liaison (mon auto, mon adorable voisine)
• ma, ta, sa apparaissent avec les noms féminins devant un mot qui ne déclenchent pas la liaison (ma voiture, ma grande auto)
• ce apparait avec les noms masculins devant un mot qui ne déclenche pas la liaison (ce matin, ce nouvel argument)
• cet, cette apparaissent avec les noms féminins (cette matinée, cette idée) ou avec un nom masculin devant un mot qui déclenche la liaison (cet argument, cet ancien militaire)

D’abord le récapitulatif de l’Académie française :

Les noms de pays s’utilisent généralement avec l’article (la France,
l’Allemagne) ; cependant, il existe quelques exceptions comme Israël,
Monaco, Madagascar, Cuba, Taïwan ou encore Haïti.

L’article disparaît toujours avec la préposition « en » (en France).
Il disparaît également après la préposition « de » indiquant l’origine
: un tapis d’Iran, un vase de Chine. C’est surtout une question
d’usage, et il n’y a pas de règle absolue, bien qu’il existe parfois
une nuance de sens plus ou moins nette : par exemple, dans le
gouvernement de la France ou l’économie de la France, la France est
désignée à un moment de son histoire, tandis que dans l’ambassade de
France, elle, est prise dans un sens intemporel.

Toutefois, l’article se maintient généralement lorsque le nom qui
précède le pays est accompagné d’un adjectif : l’Histoire de France
mais l’Histoire économique de la France.

On note aussi l’usage selon le sens avec l’origine et la dichotomie entre le moment de l’histoire par opposition au sens intemporel. Cela participe aussi, à mon avis, de la différence dont traite l’auteur Jean Bastien et à laquelle on fait référence ici et là dans les réponses.

---

On trouve au Guichet du savoir des contenus qui traitent de la question et on fait référence par exemple à un document sur les prépositions de lieu. Pour mettre en scène la règle spécifique sur l’origine, on fait le choix de poser d’abord le genre des noms de pays comme généralité et d’admettre des exceptions, pour fins d’application avec en :

Tous les pays qui se terminent en -e sont féminins.
Attention 1 :
le Mexique, le Cambodge, le Zaïre, le Zimbabwe, le Mozambique
Attention 2 : en Israël, en Iran, en Irak

…puis avec au (on note aux pour les noms aux pluriel) :

Tous les pays qui ne se terminent pas en -e + le Mexique, le Cambodge,
le Zaïre, le Zimbabwe.

Enfin on traite de l’origine en fonction du genre qu’on a posé :

• Devant les noms de pays féminins : de
  ce sont des vins de
  France
• Devant les noms masculin: du
  il est du Sénégal
• Devant les noms pluriel: des
  Vous êtes des États-Unis?
• Élision
  Ce sont des oranges d’Israël

[ Les prépositions de lieu, site de Fabienne Gérard, extraits (3) ]

---

Dans Le bon usage (Grevisse et Goosse, ed. de Boeck/Duculot), on affirme d’abord généralement au §1051 a)1 (voir en complément, départements) que les noms de pays prennent la préposition en quand ils sont féminins ou qu’ils commencent avec une voyelle, et au quand ils sont masculins et à initiale consonantique. On note aussi qu’auparavant on employait à la/à l’ plutôt que en pour les noms de pays féminins et lointains; qu’on employait même sans article avec les régions (Ma fille est partie pour Provence., Sévigné). Par ailleurs, en Danemark, en Canada restaient possibles, mais rarement, au 20^e. Ensuite on a des exceptions; Monaco et Saint-Martin prennent la préposition à. Avec les noms de pays dont l’usage de l’article n’est pas constant (par ex. Andorre), on a des hésitations entre en et à.

Et donc on se doit d’aller voir en amont le cas de l’absence de l’article devant le nom propre (§588). En principe les noms propres se passent facilement de l’article; c’est le cas des villes et îles etc., avec un tas de nuances, mais ce n’est pas le cas du nom de pays. Dans certains de ces cas on a l’article indéfini.

Quant au cas des régions, dont celui du pays, on a ordinairement l’article défini. Cependant :

• Les noms pays ne prennent pas l’article quand on utilise en (en Iran, en France)
• Quand de marque l’origine avec des noms singuliers soit féminins
  soit commençant par une voyelle, on n’utilise pas l’article (on donne
  parmi les exemples revenir d’Amérique, d’Irak, les vins d’Espagne, et celui de l’ambassade de France qu’on oppose au
  gouvernement de la France)

Puis dans un note on explique que pour les noms féminins, et les masculins qui commencent par une consonne, l’article est « *assez souvent facultatif », surtout après un pluriel (les côtes de (la) France). Étrangement on propose un cas au singulier où on montre les deux possibilités: une carte d'(ou de l’)Iran. Le pépin est que l’Iran est un nom masculin qui commence par une voyelle et non pas par une consonne(!).

---

À la Banque de dépannage linguistique (BDL), on résume la règle sur l’emploi des prépositions avec les noms de pays :

on emploie la préposition en devant les noms de pays de genre féminin
et devant tous les noms qui commencent par une voyelle (ou un h muet).
[…]
Pour les noms de genre masculin et qui commencent par une
consonne (ou un h aspiré), on emploie au, c’est-à-dire à + le.

De plus, on a une liste de tous les noms de pays avec des informations pertinentes dont le genre, le nom officiel du pays et l’emploi de la préposition adéquate (en/au) :

Allemagne, fém. / République fédérale d’Allemagne / Allemand, Allemande / Je visiterai l’Allemagne. J’irai en Allemagne.

Royaume-Uni, masc. / Royaume-Uni de Grande-Bretagne et d’Irlande du Nord / Britannique / Je visiterai le Royaume-Uni; la Grande-Bretagne; l’Écosse; l’Angleterre; le Pays de Galles; l’Irlande du Nord. J’irai au Royaume-Uni; en Grande-Bretagne; en Écosse; en Angleterre; au Pays de Galles; en Irlande du Nord.

Inde, fém. / République de l’Inde / Indien, Indienne / Je visiterai l’Inde. J’irai en Inde.

Iran, masc. / République islamique d’Iran / Iranien, Iranienne / Je visiterai l’Iran. J’irai en Iran.

Uruguay, masc. / République orientale de l’Uruguay / Uruguayen, Uruguayenne / Je visiterai l’Uruguay. J’irai en Uruguay.

On n’étaye pas quel serait le résultat de l’emploi avec de pour signifier l’origine dans ces listes. Cependant, on note un cas particulier avec Haïti (Cet écrivain est originaire d’Haïti.); on remarque que l’élision va dans le sens du nom officiel (République d’Haïti).

---

Si on tente d’appliquer cette théorie (verbe revenir = origine, + féminin ou débutant par une voyelle), on obtient les mêmes résultats que dans une autre réponse (tous avec d’). Dans le cas de l’Inde et de l’Uruguay, ça ne respecte pas le nom offi

ABC de la grammaire : le sens est prioritaire aux règles tout simplement !
je viens de l’allemagne veut dire du terroir, de l’histoire, de la vraie.
je viens d’allemagne veut dire administrativement hors des frontières d’ici.
Une distinction similaire existe pour les us; united states ou states est utilisé par les étrangers mais united states of america par les vrais citoyens américains.